大厂Android面试题汇总（三）数据结构

• 常用数据结构简介
  数据元素相互之间的关系称为结构。
  有四类基本结构：集合、线性结构、树形结构、图状结构。
  1，集合结构：除了同属于一种类型外，别无其它关系。
  2，线性结构：元素之间存在一对一关系常见类型有:?数组,链表,队列,栈,它们之间在操作上有所区别。
  　　例如：链表可在任意位置插入或删除元素,而队列在队尾插入元素,队头删除元素, 栈只能在栈顶进行插入,删除操作.
  3，树形结构：元素之间存在一对多关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)。
  4，图形结构：元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。
• 并发集合了解哪些？
  竟一个都没用过
  并发集合类
• 列举java的集合以及集合之间的继承关系
  继承关系
  java集合继承关系及特点

• 集合类以及集合框架

  
  完整集合框架
• 容器类介绍以及之间的区别（
  容器类估计很多人没听这个词，Java容器主要可以划分为4个部分：List列表、Set集合、Map映射、工具类（Iterator迭代器、Enumeration枚举类、Arrays和Collections），具体的可以看看这篇博文 Java容器类）
• List,Set,Map的区别
  详见上边各帖
• List和Map的实现方式以及存储方式
  详见上边各贴
• HashMap的实现原理
  HashMap的实现原理
  HashMap实现原理及源码分析
• HashMap数据结构？
  见上
• HashMap源码理解
  见上
• 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;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 获取指定 bucketIndex 索引处的 Entry  
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // 如果 Map 中的 key-value 对的数量超过了极限
    if (size++ >= threshold)
    // 把 table 对象的长度扩充到原来的2倍。
        resize(2 * table.length);
}

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

static int indexFor(int h, int length) {  
    return h & (length-1);
}

//获取
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;
    }
    return null;
}

简单来说就是将Entry根据hash算法放入数组的链表中的一个过程
详见上

• HashMap怎么手写实现？
  见上
• ConcurrentHashMap的实现原理
  Java并发包中提供的一个线程安全且高效的HashMap实现，策略就是分段锁机制。
  ConcurrentHashMap实现原理及源码分析
• ArrayMap和HashMap的对比
  ArrayMap和HashMap区别
• HashTable实现原理
  HashTable的使用和原理
• TreeMap具体实现
  TreeMap
• HashMap和HashTable的区别
  （1）基类不同：HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是什么？它是任何可将键映射到相应值的类的抽象父类，而AbstractMap是基于Map接口的骨干实现，它以最大限度地减少实现此接口所需的工作。
  （2）null不同：HashMap可以允许存在一个为null的key和任意个为null的value，但是HashTable中的key和value都不允许为null。
  （3）线程安全：HashMap时单线程安全的，Hashtable是多线程安全的。
  （4）遍历不同：HashMap仅支持Iterator的遍历方式，Hashtable支持Iterator和Enumeration两种遍历方式
• HashMap与HashSet的区别
  两者区别
  HashMap和HashSet的区别
• 集合Set实现Hash怎么防止碰撞
  Java集合---HashSet的源码分析
• ArrayList和LinkedList的区别，以及应用场景
  1,如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；
  2,如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；
  ArrayList和LinkedList区别及使用场景
• 数组和链表的区别
  数组 分配内存连续，长度固定，插入，删除操作效率低
  链表 分配内存不连续，长度不固定，插入，删除操作效率高
• 二叉树的深度优先遍历和广度优先遍历的具体实现

public void depthFirst() {  
    Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();  
    Map<String, Object> node = new HashMap<String, Object>();  
    nodeStack.add(node);  
    while (!nodeStack.isEmpty()) {  
        node = nodeStack.pop();  
        System.out.println(node);  
        //获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点  
        List<Map<String, Object>> children = getChildren(node);  
        if (children != null && !children.isEmpty()) {  
            for (Map child : children) {  
                nodeStack.push(child);  
            }  
        }  
    }  
}  
​//节点使用Map存放  

public void breadthFirst() {  
    Deque<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();  
    Map<String, Object> node = new HashMap<String, Object>();  
    nodeDeque.add(node);  
    while (!nodeDeque.isEmpty()) {  
        node = nodeDeque.peekFirst();  
        System.out.println(node);  
        //获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点  
        List<Map<String, Object>> children = getChildren(node);  
        if (children != null && !children.isEmpty()) {  
            for (Map child : children) {  
                nodeDeque.add(child);  
            }  
        }  
    }  
}  
//这里使用的是双端队列，和使用queue是一样的  

Java遍历树（深度优先+广度优先）

• 堆的结构
  特殊的一种树
  基本数据结构――堆的基本概念及其操作
  彻底弄懂最大堆的四种操作(图解+程序)（JAVA）

• 堆和树的区别
  二叉排序树与堆的区别

• 堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？
  堆和栈的区别（内存和数据结构）

• 什么是深拷贝和浅拷贝
  直接赋值：两变量指向同一对象，对任一变量操作发生变化，两变量均改变。
  浅拷贝：创建一个新对象，然后将当前对象的非静态字段复制到该新对象，如果字段是值类型的，那么对该字段执行复制；如果该字段是引用类型的话，则复制引用但不复制引用的对象。因此，原始对象及其副本引用同一个对象。（String是引用类型，但是有值类型特性）
  深拷贝：创建一个新对象，然后将当前对象的非静态字段复制到该新对象，无论该字段是值类型的还是引用类型，都进行复制。（在浅拷贝的基础上，每次拷贝将引用类型创建新对象）
  一看就懂的，java深拷贝浅拷贝

• 手写链表逆序代码
  单链表反转java代码

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

• 讲一下对图的理解
  浅析数据结构-图的基本概念

• 判断单链表成环与否？
  判断单链表成环与否

• 合并多个单有序链表（假设都是递增的）
  合并k个有序的链表

问题来自：AWeiLoveAndroid的博客