Android学习笔记八:Java常用数据结构

2018-03-26 00:04 评论 0 条

摘要:

最近在整理Android岗位面试题答案,虽然工作已有两年,独立开发了好几个APP,但在不查资料的情况下,回答这些试题非常的困难,瞬间感觉一万点伤害。即使不为了找工作,整理这样一份Android面试题答案,也可以加深对各个知识点的理解,这一整套面试题基于《最全的BAT大厂面试题整理》,然后将每一个分类拆分成附带参考答案的独立的文章,在此非常感谢整理试题的原作者。

Android学习笔记六:Java基础知识

Android学习笔记七:Java源码深入学习

Android学习笔记八:Java常用数据结构

Android学习笔记九:Java线程、多线程和线程池(27号更新)

Note that:文章中给出的答案尽管参考了网上的很多资料,但肯定回答得还不够到位,更需要在实际的环境中运用、验证(有木有推荐岗位哈)

  • 常用数据结构简介

常用的数据结构有:数组、链表、栈、队列、散列、树

  • 并发集合了解哪些?
常用并发集合 举例
并发List Vector、CopyOnWriteArrayList
并发Set CopyOnWriteArraySet、ConcurrentSkipListSet
并发Queue ArrayBlockingQueue、ConcurrentLinkedQueue、LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、SynchronousQueue
并发Deque ConcurrentLinkedDeque、LinkedBlockingDeque

详情:

Vector和CopyOnWriteArrayList是线程安全的。

区别:

Vector给每个方法添加了synchronized同步锁,保证多个线程同时访问add()get()remove()等方法的安全,但不保证遍历的线程安全(即一个线程遍历,另外一个线程执行添加、删除或其他),为了保证遍历的安全,需要给遍历的Vector对象添加同步锁

CopyOnWriteArrayList的实现原理,每个线程访问的是CopyOnWriteArrayList的一个副本,最后将原对象引用指向最后的CopyOnWriteArrayList的地址,保证线程安全

如何线程安全地遍历List:Vector、CopyOnWriteArrayList
https://www.cnblogs.com/wucao/p/5350461.html

CopyOnWriteSet的实现原理和CopyOnWriteArrayList一样,通过对副本进行访问,最后将引用指向该地址

Queue和Deque,前者是普通的队列,后者是双端的队列,双端队列是指队列的头部(或尾部)可以进行入队操作和出队操作

Java中的queue和deque
http://blog.csdn.net/shf4715/article/details/47052385

  • 列举java的集合以及集合之间的继承关系

List集合

ArrayList集合:

ArrayList继承关系

LinkedList集合:

LinkedList继承关系

Vector集合

Vector继承关系

Map集合

HashMap集合:

HashMap继承关系

LinkedHashMap集合:

LinkedHashMap继承关系

TreeMap集合

TreeMap继承关系

HashTable集合

HashTable继承关系

Properties集合

Properties继承关系

备注PropertiesHashTable是Map接口的历史属性

Set集合

HashSet集合

HashSet继承关系

LinkedHashSet集合

LinkedHashSet继承关系

TreeSet集合

TreeSet继承关系

Android Studio UML插件用法

Queue集合

PriorityQueue集合

PriorityQueue继承关系

  • 集合类以及集合框架

Deque集合

ArrayDeque集合

ArrayDeque继承关系

Collection体系

Collection集合框架

Map体系

Map集合框架

Java集合类详解
http://blog.csdn.net/u014136713/article/details/52089156

  • 容器类介绍以及之间的区别

Java容器类
http://alexyyek.github.io/2015/04/06/Collection/

  • List,Set,Map的区别

Set集合

不允许存储a.equlas(b)两个相同的对象,否则,后存储的对象会代替已存在的对象

Set接口相关方法

List集合

允许存储a.equals(b)两个相同的对象,同时允许存储多个null值,可以根据元素的整型索引快速访问元素

除了具备Set集合提供的方法外(Set、List都继承自Collection接口),还添加了多个根据索引访问、修改元素的方法

List接口相关方法

Map集合

不允许存储重复的键,同时不允许将自身对象作为键存储,但允许将自身对象作为值存储

  • List和Map的实现方式以及存储方式

ArrayList,以数组表的方式存储数据,允许存储相同的对象,方便快速地通过索引查询

LinkedList,以链表的方式存储数据,允许存储相同的对象,适合频繁地插入、删除操作

Vector,除了支持同步操作外,和ArrayList基本一样

HashMap,以分散数组表的方式存储数据,不允许存储键相同的对象,同时也不允许将自身对象作为键存储,但可以将自身对象作为值存储,也可以存储值相同的对象

LinkedHashMap,以分散链表的方式存储数据,继承自HashMap,优化了数据的插入、删除操作

TreeMap,以二叉查找树的方式存储数据,除了具备Map集合的特点外,TreeMap还对存储的数据进行排序

List、Map、Set按存储方式说说都是怎么存储的?
http://blog.csdn.net/Mr_linjw/article/details/51335490

几种 Map 内部存储方式的介绍( 以 Java 为例讲解 )
http://blog.csdn.net/weixinzhang/article/details/50614438

  • HashMap的实现原理

为了提高查询的效率和减少空间的浪费,初始化HashMap的容量大小必须是2的n次方

尽量避免扩充容量,防止扩容对性能造成影响。扩容后的HashMap,需要重新计算已存在数据的在新数组中的位置,扩容后的大小是原来的两倍

默认负载因子0.75,是对时间和空间的平衡选择

快速失败策略,HashMap不是线程安全的,在进行迭代的时候有其他线程修改了map,会抛出ConcurrentModificationException

HashMap,是一种数组+链表的存储方式,对数据进行迭代需要遍历两次

第一种

Map map = new HashMap();
  Iterator iter = map.entrySet().iterator();
  while (iter.hasNext()) {
  Map.Entry entry = (Map.Entry) iter.next();
  Object key = entry.getKey();
  Object val = entry.getValue();
  }

效率高,以后一定要使用此种方式!

第二种

Map map = new HashMap();
  Iterator iter = map.keySet().iterator();
  while (iter.hasNext()) {
  Object key = iter.next();
  Object val = map.get(key);
  }

效率低,以后尽量少使用!

  • HashMap数据结构?

是一个数组+链表的数据结构,内部定义了一个Entry数组,数组中的每一项又是一个链表

  • HashMap源码理解

根据实际存储数据的长度,初始化HashMap容量,初始化的容量大小必须是2的n次方,尽量避免扩充容量

默认HashMap的初始化容量为16,负载因子为0.75,它是对时间和空间的平衡选择

快速失败策略,HashMap是非线程安全的,对数据进行迭代的时候其他线程试图修改map,会抛出ConcurrentModificationException异常

  • HashMap如何put数据(从HashMap源码角度讲解)?
public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
    if (key == null)
        return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}

添加到HashMap中的数据,先判断key值是否为null,key值为null直接将value值放置在数组的第一个位置

否则,计算key值的hashCode,同时定位数组中的位置,如果该hashCode已存在,那么将value值添加到该位置的链表上;否则,直接将value值添加到数组上

HashMap的实现原理
http://www.importnew.com/16301.html

  • HashMap怎么手写实现?
public class HashMap<K,V>{
    static HashMapEntry<K,V> implement Map.Entry<K,V>{
        K key;
        V value;
        HashMapEntry<K,V> next;
        int hash;
        ...
    }
    int DEFUALT_CAPACITY=16;//定义默认的容量大小
    int DEFUALT_LOAD_FACTOR=0.75;//定义默认的加载因子
    static final HashMapEntry<?,?> EMPTY_TABLE={};//定义默认的空数组
    HashMapEntry<K,V>[] table=(HashMapEntry<K,V>[])EMPTY_TABLE;

    public HashMap<K,V>(int capacity,int loadFactor){
        this.DEFAULT_CAPACITY=capacity;
        this.DEFAULT_LOAD_FACTOR=loadFactor;
        if(table==EMPTY_TABLE){
            table=new HashMapEntry[DEFAULT_CAPACITY*DEFAULT_LOAD_FACTOR];
        }
    }
    public V put(K key,V value){
        //计算key对应的hash值
        int hash=key.hashCode();
        int i=indexFor(hash,table.length);
        //判断是否存在相同的key,存在,则覆盖
        for(HashMapEntry<K,V> e=table[index];e!=null;e=e.next){
            if(e.hash==hash&&(e.key==key||e.key.equals(key))){
                int oldValue=e.value;
                e.value=value;//覆盖旧value
                return oldValue;
            }
        }
        addEntry(hash,key,value,i);
        return null;
    }

    int indexFor(int hash,int length){
        return hash& (length-1);
    }
    void addEntry(int hash,V key,V value,int index){
        ...
    }
}
  • ConcurrentHashMap的实现原理

除了具备HashMap的特点外,ConcurrentHashMap是线程安全的,采用的是分段锁技术,比其他同步锁的方式(HashTableCollections.synchronizedMap())性能更高

分段锁技术,指的是ConcurrentHashMap加锁的是Map.Entry对象,在JDK_1.8.0_51版本,使用的是synchronized同步代码块,由JVM自动添加并释放锁;而在其它JDK版本也有使用Lock方式的

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        ...
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;//Node继承自Map.Entry
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                ...
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                //使用synchronized同步代码块,加锁的是Node对象
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                    ...
                    }
                }
                ...
            }
        }
        addCount(1L, binCount);
        return null;
    }

ConcurrentHashMap原理分析

http://www.importnew.com/16142.html
ConcurrentHashMap实现原理
http://blog.csdn.net/dingji_ping/article/details/51005799

  • ArrayMap和HashMap的对比

ArrayMap的数据存储方式,使用的是两个小数组,一个数组按顺序存储key对应的hash值,一个数组根据key的顺序存储key-value值,查询的时候在第一个数组中获取hash值的索引,再由索引在后一个数组获取value值

HashMap的数据存储方式,使用的是数组+链表,根据key对应的hash值检索数组是是否存在对应的value值,如果不存在,直接将value存储到索引所在位置;如果存在,将放置在该位置的链表头部

区别:

ArrayMap数据的访问速度比HashMap更快,适合应用在数据量不多(1000以内),访问操作频繁,插入和删除较少的场景

  • HashTable实现原理

HashTable,是以数组+链表的方式存储数据,数组存储的是key对应的hash值

HashTable的方法是同步的,说明它是线程安全的,继承自Dictionary,实现Map接口

HashTable默认容量大小为11,默认加载因子为0.75(分析JDK1.8_)

HashTable的key、value都不可以为null

Java 集合系列11之 Hashtable详细介绍(源码解析)和使用示例
http://www.cnblogs.com/skywang12345/p/3310887.html

  • TreeMap具体实现

...

红黑树数据结构剖析
http://www.cnblogs.com/fanzhidongyzby/p/3187912.html

红黑树系列集锦
http://blog.csdn.net/v_JULY_v/article/category/774945

Java提高篇(二七)-----TreeMap
http://blog.csdn.net/chenssy/article/details/26668941

  • HashMap和HashTable的区别

HashMap、HashTable存储数据的方式是一样的,都是数组+链表的方法

HashMap允许key、value为null,如果key为null,直接将value存储到数组的第一个位置;HashTable不允许key、value为null,如果value为null,抛出NullPointException异常

HashMap是非线程安全的;HashTable相关方法添加了synchronized同步锁,是线程安全的

HashMap快速失败机制,在遍历数据的时候其它线程试图修改、删除HashMap数据,会抛出ConcurrentModificationException异常

  • HashMap与HashSet的区别

数据结构不一样。HashMap是以数组+链表的方式存储数据,数组存储的是HashEntry实体,每个HashEntry实体保存key和value,同时持有指向下一个元素的引用next;

HashSet的内部实现,实例化一个HashMap对象,将要存储的数据作为HashMap对象的key,将一个固定Object对象PRESENT作为value

HashMap中不允许重复的键;HashSet不允许存储相同的对象,如果存储两个相同的对象,后存储的对象会覆盖已存储的对象

HashMap继承自AbstractMap,实现Map接口;HashSet继承自AbstractSet,实现Set接口

HashMap和HashSet的区别
http://www.importnew.com/6931.html

  • HashSet与HashMap怎么判断集合元素重复?

比较集合中是否存在当前对象的hash值,如果已存在,再通过equals方法比较两个对象是否相同,如果hash值一样同时equals比较相同,则判断它们是重复的元素

所以,存储到HashSet和HashMap集合中的元素重写equals方法的同时需要重写hasCode方法,否则使用默认的equals方法和hashCode方法

  • 集合Set实现Hash怎么防止碰撞

出现碰撞的原因,是因为存储到Set集合的对象定位到Entry数组相同的位置数组的index由存储对象的hash值和数组的length长度决定,即index=hash & (length-1)

优化过的hash值和2的n次方的length长度,使得元素的分布更加的均匀,发生碰撞的几率减少,从而有效地防止碰撞

  • ArrayList和LinkedList的区别,以及应用场景

ArrayList继承自AbstractList,实现List接口、RandomAccessFile接口,以数组的方式存储数据

LinkedList继承自AbstractSequentialList,实现List接口、Deque接口,以链表的方式存储数据

数组的方式存储数据,方便快速查询元素,适合应用于查询多,删除和插入较少的场景

链表的方式存储数据,删除和删除元素时,不需要移动元素的位置,性能方面比ArrayList更优,适合应用于删除和插入较多的场景

  • 数组和链表的区别

数组的方式存储数据,元素在内存中是连续存放,可以通过下标快速访问数组中任一元素,当插入或删除一个元素时,需要移动大部分的元素

链表的方式存储数据,元素在内存中不是顺序存放,一个元素持有下一个元素的引用,将指针指向下一个元素,依次类推,当查询元素时,需要依次遍历链表中的各个元素

  • 二叉树的深度优先遍历和广度优先遍历的具体实现

二叉树遍历算法

深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。以上面二叉树为例,深度优先搜索的顺序为:ABDECFG。怎么实现这个顺序呢?深度优先搜索二叉树是先访问根结点,然后遍历左子树接着是遍历右子树,因此我们可以利用堆栈的先进后出的特点,现将右子树压栈,再将左子树压栈,这样左子树就位于栈顶,可以保证结点的左子树先与右子树被遍历。

public static void print(BinaryTreeNode node){

    System.out.println(node.value);
}
public static void preOrder(BinaryTreeNode node){
    if(node!=null{
        print(node)
        preOrder(node.left);
        preOrder(node.right);
    }
}

广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索,是从根结点开始沿着树的宽度搜索遍历,上面二叉树的遍历顺序为:ABCDEFG.
可以利用队列实现广度优先搜索

public static void levelOrderTranversal(BinaryTreeNode root){
    Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
    if(root!=null){
        queue.add(root);
        while(!queue.isEmpty){
            BinaryTreeNode node=queue.poll();
            print(node);
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
    }
}

树的深度优先遍历和广度优先遍历的原理和java实现代码
http://outofmemory.cn/code-snippet/4189/biinary-tree-java
二叉树的广度优先遍历、深度优先遍历的递归和非递归实现方式
https://www.cnblogs.com/gl-developer/p/7259251.html

  • 堆的结构

堆的结构,是一颗完全二叉树

完全二叉树,是指除底层外,其余各层任意节点的子节点数都达到了最大数,底层的所有节点都连续集中在左边

完全二叉树

基本数据结构——堆(Heap)的基本概念及其操作

https://www.cnblogs.com/JVxie/p/4859889.html

  • 堆和树的区别

将满足结构性的树称为堆,堆也可以说是一种树

结构性,指的是除底层外,其余各层任意节点的节点数都达到了最大数,底层的所有节点都连续集合中左边

二叉堆,指的是满足堆的结构性,同时任意节点的值小于其所有子节点的值

  • 堆和栈在内存中的区别是什么

堆,是jvm管理的最大一块内存,同时也是Java GC主要的区域,堆是用来存储对象实例和数组值,所有线程共享

栈,分为Native方法栈和JVM 栈,前者主要是存储Native方法的状态;后者是线程私有的,每个方法在调用的时候,都会创建一个栈帧,栈帧存储有局部变量等信息,方法被调用时,栈帧被压入JVM栈中,方法执行完成,栈帧出栈

JVM内存管理及GC机制
http://blog.csdn.net/suifeng3051/article/details/48292193

  • 什么是深拷贝和浅拷贝

深拷贝也叫深克隆,将原对象的所有字段拷贝到副本中。不可是原对象的值类型字段,还是引用类型字段,在副本中都会被重新的创建并赋值,对副本值类型字段或引用类型字段的修改不会影响原类型,实现Cloneable接口,覆盖close方法

浅拷贝也叫浅克隆,将原对象的所有字段拷贝到副本中,对副本中值类型字段的修改不会影响原类型,但对副本中引用类型字段的修改会影响原类型,实现Cloneable接口,重写close方法

Java中的深拷贝和浅拷贝
http://blog.csdn.net/chjttony/article/details/7477346

  • 手写链表逆序代码
public static Node  reverseSingleList(Node node){
    Node p1,p2=null;
    p1=node;//记录node节点本身地址
    while(node.next!=null){
        p2=node.next;//记录node节点引用地址
        node.next=p2.next;//记录新节点持有的引用地址
        p2.next=p1;//改变指针指向
        p1=p2;//记录新的节点本身地址
    }
    return p2;
}

java 实现单链表的逆序
http://blog.csdn.net/u012571415/article/details/46955535

Java单链表的逆序
http://blog.csdn.net/wxm349810930/article/details/46724691

链表逆序(JAVA实现)
https://www.cnblogs.com/jsczljh/p/3765720.html

  • 讲一下对树,B+树的理解

树是一种由一个根节点和无数个子节点组成的数据结构,除根节点外,每一个子节点都拥有一个父节点和无数个子节点,常用的树的集合有TreeMap、TreeSet

B+树是其中一种...

从B树、B+树、B*树谈到R 树
http://blog.csdn.net/v_july_v/article/details/6530142

B树和B+树的总结
https://www.cnblogs.com/George1994/p/7008732.html

在线可视化树操作
https://www.cs.usfca.edu/~galles/visualization/BTree.html

  • 讲一下对图的理解

...

  • 判断单链表成环与否?

public class SingleList{
    static class Node {
        int value;
        Node next;

        public Node(int i){
            this.value=i;
        }
    }
    /**
     *创建一条单链表
     *@params head 表示单链表开始位置
     *@params length 表示单链表的长度
     */
    public Node createSingleList(Node head,int length){
        if(head==null){
            return null;
        }
        Node p1=head;//记录开始的内存地址
        int i=0;
        while(i<length){
            Node node=new Node(i);
            p1.next=node;//记录持有的引用地址
            p1=node;//移动指针到下一个节点
            i++;
        }
        return head;//返回开始的列表地址
    }

    /**
     *判断一条单链表是否成环
     *@params node 传入的单链表
     *@return 成环,返回true;否则,返回false
     */
    public boolean loopSingleList(Node node){
        if(node==null||node.next==null){
            return false;
        }
        Node p1,p2;//定义两个节点记录指针开始位置
        p1=node;//指针p1每次向前移动一步
        p2=node;//指针p2每次向前移动两步
        Node last;
        while((last=p2.next)!=null&&last.next!=null){
            p1=p1.next;
            p2=last.next;
            //不断移动之后,找到两个地址一样的节点
            if(p1==p2){
                return true;
            }
        }
        return false;
    }
}

面试算法:链表成环的检测
https://www.jianshu.com/p/6ff4f6cef1d0

判断单链表是否成环算法
http://blog.csdn.net/fu908323236/article/details/78205462

  • 链表翻转(即:翻转一个单项链表)
pulibc void reverseSingleList(Node head){
    Node p1,p2=null;
    p1=head;//记录节点内存地址
    while(head.next!=null){
        p2=head.next;//记录节点持有的引用地址
        head.next=p2.next;//记录下一个节点持有的引用地址
        p2.next=p1;//改变节点的指针指向
        p1=p2;//记录下一个节点内存地址
    }
    return p2;
}
  • 合并多个单有序链表(假设都是递增的)

思路:依次比较两个有序单链表,将较小的单链表的节点提取出来,组成一个新链表,最后将没有遍历结束的链表的引用赋值给新链表


public static Node mergeSingleListOrdered(Node firstSingleListOrdered,Node secondSingleListOrdered){
    Node p1=firstSingleListOrdered;
    Node p2=secondeSingleListOrdered;
    if(p1==null){
        return p2;
    }else if(p2==null){
        return p1;
    }
    Node newHead=null;
    if(p1.value<p2.value){
        newHead=p1;//记录新链表开始位置
        newHead.next=mergeSingleListOrdered(p1.next,p2);
    }else{
        newHead=p2;//新链表开始位置
        newHead.next=mergeSingleListOrdered(p1,p2.next);
    }
    return newHead;
}

合并两个有序递增的链表,使得合并后新链表还是有序的
http://blog.csdn.net/jcm666666/article/details/52280623

参考资料:《最全的BAT大厂面试题整理

当前文章价值9.36元,扫一扫支付后添加微信提供帮助!(如不能解决您的问题,可以申请退款)

你可能感兴趣的文章

来源:每日教程每日一例,深入学习实用技术教程,关注公众号TeachCourse
转载请注明出处: https://www.teachcourse.cn/2609.html ,谢谢支持!

资源分享

浅谈ActionBar的使用 浅谈ActionBar的使用
Android电脑局域网操作手机的工具 Android电脑局域网操作手机的工
Android开发深入理解WebChromeClient之onShowFileChooser或openFileChooser使用说明 Android开发深入理解WebChrom
自我介绍模板 自我介绍模板