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

摘要：

最近在整理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集合：

LinkedList集合：

Vector集合

Map集合

HashMap集合：

LinkedHashMap集合：

TreeMap集合

HashTable集合

Properties集合

备注：Properties和HashTable是Map接口的历史属性

Set集合

HashSet集合

LinkedHashSet集合

TreeSet集合

Android Studio UML插件用法

Queue集合

PriorityQueue集合

• 集合类以及集合框架

Deque集合

ArrayDeque集合

Collection体系

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)两个相同的对象，否则，后存储的对象会代替已存在的对象

List集合

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

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

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是线程安全的，采用的是分段锁技术，比其他同步锁的方式（HashTable、Collections.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大厂面试题整理》