数据结构

线性表

ArrayList、LinkedList和Vector的异同以及底层数据结构是

1
2
3
4
5
1、ArrayList  底层：是数组结构，查询快，增删慢，线程不安全，效率高。

2、LinkedList底层：是链表数据结构，查询慢，增删快，线程不安全，效率高。

3、Vector      底层：是数组结构，查询快，增删慢，线程安全，效率低。

ArrayList如何动态扩展

1
2
3
4
5
6
7
8
9
10
// 初始化：
1. ArrayList()会使用长度为 0 的数组
2. ArrayList(int initialCapacity)会使用指定容量的数组
3. public ArrayList(Collection<? extends E> c)会使用 c 的大小作为数组容量
    
// 添加：
1. add(Object o)首次扩容为 10，再次扩容为上次容量的1.5倍
2. addAll(Collection c) 
    2.1 没有元素时，扩容为Math.max(10,实际元素个数)
    2.2 有元素时，扩容为Math.max(原容量1.5倍,实际元素个数)

HashMap

HashMap的底层数据结构

1
2
3
JDK1.7 数组+链表

JDK 1.8 数组+（链表/红黑树）

为何要用红黑树

1
2
1.数值较大时，使用红黑树可以优化查询性能
2.可以避免DoS攻击，防止有人恶意使用多个hashcode一样的值注入攻击，避免链表超长性能下降

为何一上来不树化

1
2
3
4
数值较小时，链表的查询性能、内存占用较优于红黑树，所以不需要一上就树化
查找更新的时间复杂度是O(log<sub>2</sub>n)
TreeNode占用空间也比普通Node要大
如非必要尽量使用链表

树化阈值为何是8

1
hash表内按泊松分布，在负载因子是0.75的情况下，长度超过8的链表出现概率是0.00000006，选择8是为了让树化几率足够小

何时会树化

1
链表长度超过树化阈值8；数组容量>=64

何时会退化为链表

1
2
情况1：在扩容时如果树被拆分了，且树的元素个数<=6则会退化成链表
情况2：remove树节点时，若移除节点之前root、root.left、root.right、root.left.left有一个为null时，也会退化成链表

索引如何计算

1
计算对象的hashCode()，再进行HashMap的hash()方法进行二次哈希，最后hash 求模% 或 &(capacity - 1) 得到索引

为什么要二次哈希

1
二次哈希是为了综合高位数据，让哈希分布更为均匀

数组容量为何是2的n次幂

1
2
3
1.计算索引时，2的n次幂可以使用位与运算取代取模，效率更高
2.扩容时可以根据hash & oldCap == 0 来判断元素是否留在原来位置，否则 新位置 = 旧位置 + oldCap
3.是为了配合索引计算、二次哈希的优化手段，例如HashTable的容量就不是2的n次幂，并不能说那种设计更优，应该是设计者综合了各种因素，最终选择了使用2的n次幂作为容量

HashTable与HashMap的区别

HashMap 线程不安全 允许有null的键和值 效率高一点 方法不是Synchronize的 有containsValue和containsKey方法
HashTable 线程安全 不允许有null的键和值 效率稍低 方法是Synchronize的 有contains方法方法

HashMap的扩容机制

1
2
3
4
1. HashMap的容量是有上限的，必须小于 1 << 30，也就是2的30次幂 = 1073741824
2. 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度是16
3. 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量。
4. 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

HashMap是不是线程安全的

1
2
不是，会发生数据错乱
并发情况下使用ConcurrentHashMap

HashMap的put元素的过程

1
2
3
4
5
6
7
8
9
1. HashMap是懒惰创建数组的，首次使用才创建数组
2. 计算索引（桶下标）
3. 如果桶下标没有被占用，创建Node占位返回
4. 如果桶下标已经被占用
	4.1 如果节点是TreeNode走红黑树的添加或更新逻辑
	4.2 如果节点是Node，走链表的添加或更新逻辑
		4.2.1 如果添加时超过树化阈值且容量大于64，走树化逻辑
5. 返回容量是否超过阈值，一旦超过就进行扩容
	5.1 如果进行扩容，要对旧元素重新计算索引

为什么加载因子是0.75

1
2
3
1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表会比较长，影响性能
3. 小于这个字，冲突减少了，但扩容会比较频繁，空间占用多

Node的数据结构

1
2
3
4
5
6
7
// 链表节点结构
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

寻址算法

1
2
3
4
5
// 将高16位和低16位进行了异或运算
static final int hash(Object key){
    int h;
    return (key == null) ? 0 : (h = key.hashColde()) ^ (h >>> 16);
}

树

红黑树的数据结构，左旋和右旋是怎样实现的

  • 所有节点非红即黑
  • 根节点是黑色
  • 叶子节点是黑色
  • 不能有连续的红色
  • 任意节点到叶子节点路径中有相同数量的黑色节点
1
2
3
左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋以父节点作为左旋

右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋

什么是Huffman树

1
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

Huffman树的用途

1
哈夫曼编码

Huffman树什么情况下压缩效率高

B树和B+树

1
2
3
4
5
6
B树也称为B-树

B+树是B-树的一种变体

B+树把数据存放在叶子节点上，并有序排列，这样做刚好适用于范围查询
B+树最终会呈现出一个矮胖地形式，B-树则是高瘦

对TreeMap的理解

TreeMap的底层数据结构

1
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
面经

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！