HashMap

Posted on | In
Words count in article: 1.7k | Reading time ≈ 6

java里hashmap是如何实现的？

JDK1.7：数组+链表
JDK1.8：数组+链表+红黑树

HashMap 为什么线程不安全？为什么ConcurrHashMap线程安全？

jdk 1.7使用的是头插法，在多线程环境下，使用HashMap的put操作会引起死循环，原因是多线程会导致HashMap的Entry链表形成环形数据结构，导致Entry的next节点永远不为空，就会产生死循环获取Entry。
ConcurrentHashMap 采用分段锁的方式，即每一段数据配一把锁，当一个线程占用其中一段时，其它段的数据仍然可以put或get。

ConcurrentHashMap的具体实现

底层分段数组+链表，线程安全。把Map分为N个Segment，提供相同的线程安全，允许多个修改并发，可以段内扩容。
ConcurrentHashMap由Segment数组结构和HashEntry数组结构组成；
Segment是一种可重入锁（ReentrantLock），HashEntry用于存储键值对数据；
一个ConcurrentHashMap包含一个由若干个Segment对象组成的数组，每个Segment对象守护整个散列映射表的若干个桶，每个桶是由若干个HashEntry对象链接起来的链表，table是一个由HashEntry对象组成的数组，table数组的每一个数组成员就是散列映射表的一个桶。
把“碰撞”的HashEntry对象链接成一个链表。由于HashEntry的next域为final型，所以新节点只能在链表的表头处插入。（头插法）

hashArray和list有什么区别？

ConcurrentHashMap的扩容过程

ConcurrentHashMap多线程rehash的整体流程

ConcurrentHashMap某个桶内超过八个结点会树化，什么情况下超过八个结点不会树化

链表超过了八个结点但是数组大小没有超过64时会进行扩容而不是树化

HashMap 1.7 / 1.8 的区别，在JDK1.8中有哪些改进？

1.8加入了红黑树。只要用的还是链表，就一直有可能出现链表长度过于长的问题。链表插入效率高查询效率低，红黑树的插入和查询效率都不错。为什么不用别的树，是基于综合考虑：不仅要保证put的效率也要保证get的效率，红黑树的插入和查询效率相同，是一个折衷的考虑。
1.8加入了treeify树化的阈值（默认为8），含义是某个index上链表元素大于等于8时需要将链表改成红黑树，8个元素了此时查询效率较低。当一个红黑树结点不足6个就untreeify改成链表。这两个阈值不等的原因是为了防止在临界值进行插入or删除导致的频繁的数据结构转变。
1.8中初始化和扩容都在resize()函数中。
1.7中元素直接是Entry，1.8的元素称为Node，其中的属性都是一样的，红黑树中结点是TreeNode，TreeNode既是一个树节点又是一个双向链表结点（包含属性prev和next）
1.8中如果到达了树化阈值也不一定会树化，如果数组长度小于最小树化容量(MIN_TREEIFY_CAPACITY默认为64)，则会进行扩容而不是继续树化。因为这种情况下通过扩容，大概率也可以缩短这个链表而不需要树化。如果数组大小已经超过64了，那么处于节省内存空间的考虑，会选择树化而不是扩容。
因此在1.8中只有当插入之前链表元素大于等于8且数组大小超过64的情况下会转换成红黑树
1.8在扩容时应用了扩容的规律，即如果新的有效最高位是1则index是原index+原数组大小。
1.8中没有rehash，即1，8在扩容过程中不会重新计算hashcode
1.8中链表转红黑树首先把链表上每个结点改为TreeNode，在头结点上开始遍历，更改每个结点关于红黑树的属性即可（红黑树的根节点一定是黑色的）。比较过程先比较hash值再比较key的大小，若仍然相同则比较key的class再比较内部hash值（identityHashCode即jdk自带的hash值）

ConcurrentHashMap 1.7 / 1.8 的区别，在JDK1.8中有哪些改进？

为什么 HashMap的size为2的幂次方 ？

方便减一做与运算计算index。

HashMap resize()过程能否介绍 ？

resize()即扩容过程。如果没有扩容机制，即数组大小固定，那么如果元素很多，一定会出现链表太长的情况，get()方法效率降低。扩容会新建一个大小翻倍的Entry数组，再使用transfer()方法将已有元素转移到新的数组上：根据元素已包含的hash值(hashcode)来计算在新数组中的index。原本index相同的两个元素可能位置仍然相同也可能相差原始数组的大小，因为只可能是新的最高有效位有区别，低k位一定相同(因为原来在同一位置)。
JDK 7中循环数组遍历链表，如果key为null则hash值为0，否则就是这个key的hash值。在新的数组容量下重新计算index，用头插法插入这个元素。key为null是一定存放在index = 0的位置。transfer过程中会判断是否需要重新计算hashcode，默认不会重新计算(rehash = false)。
JDK 8中计算e.hash & oldCapacity，假设oldCapacity是2的k次幂则它的二进制表示中只有k+1位是1，这个与运算是在判断e.hash的第k+1位是否为0，如果是0，则index不变（低位lo），如果是1，则index += oldCapacity（高位hi）。对原始数组某一位置上的链表，逐个做与运算，根据结果分成两条链（尾插法形成链），直接放到新数组的lo和hi位。对于原始数组某一位置上的红黑树，分成两棵树，如果子树的元素总数小于untreeify的阈值（6）则转换成链表，否则转换成红黑树（如果没有分裂，则等价于将原始红黑树转移），分裂出新的树的时候需要对树进行调整并将新的root挪到链表的起点。

HashMap效率受什么影响？

(负载因子、hash数组size)

HashMap中扰动函数的作用 ？

HashMap中put如何实现（向hashmap插入(key, value)）

原理：

  1. （JDK1.7实现）判断是否为空table，如果为空，则初始化一个数组。要么使用默认容量16，要么使用传入的容量。在初始化过程中找到不小于这个容量的最小的2的幂(roundUpToPowerOf2(tosize))。比如传入initialCapacity为10，则初始化数组大小为16。最大容量是2^30(1<<30)。重算扩容的阈值（min(capacity * loadfactor, max_capacity + 1)）。hashmap的参数：initialcapacity, loadfactor （初始容量默认16和加载因子默认0.75）entry包含四个属性：key，value，next(Entry)，hash值(int)。hash值用于两个Entry对象的比较。

  2. 计算hashcode
    调用hash方法：调用key.hashCode()方法并与hash seed做异或运算，再对这个值进行右移或者异或运算。右移相当于高位移动到了低位，低位省略了，异或从而使得高位也可以参与index的计算，使index更平均（异或^：相同为0，不同为1）。hashCode方法可以重写。将计算好的hashCode存入Entry的hash属性。
    1.8中仍然时右移和异或，只是没有1.7那么复杂，key为null时hashcode为0。

  3. 计算index
    即：根据hashCode值计算数组下标。
    计算key.hashCode() & (table.length - 1) （二进制位运算速度快。table.length是2的k次幂，table.length - 1的低k位全1高位全0，该与操作相当于只保留了key的hashcode的后k位作为index，index的取值范围正好是0到table.length - 1）作为该entry存放在数组中的index。hashmap放入一个键值对时，将该键值对视作一个entry，把这个entry的引用放入数组的某个位置or这个位置连接的链表上，这个位置即index，需要通过key的值来计算。如果取余，很容易冲突（不同key放在数组的同一位置），且取余操作比位操作慢。

  4. (JDK1.7中先扩容再添加，JDK1.8是先添加再扩容)扩容：1.7中，如果元素个数超过阈值且当前要放入的index处不为null则开始扩容。1.8中只判断了元素个数超过阈值就扩容。扩容方法：resize()
    1.7在数组的每次扩容时会判断是否需要扩容，需要扩容时会改变hashseed，使得计算出的hashcode更加分散。

  5. 如果当前数组的当前index处为空，则新建一个Entry对象，包含key，value，hash和null（next为空）直接放入index处。否则在JDK 1.7中使用头插法：(key, value, hash, header)，其中header是链表头部，即table[index]，再把这个Entry放入table[index]，添加之后size++；而在1.8中使用尾插法，因为本来就需要遍历整个链表来判断元素个数是否达到treeify的阈值，同时在遍历链表时可以判断是否已经存在整个key，如果存在则直接覆盖，如果当前元素的key不相等，则判断当前元素的结点是否instanceof TreeNode，如果已经是一个树的则直接进行红黑树TreeNode结点的插入，否则当前index一定是链表，循环并累计链表上结点个数，对每个结点判断是都需要覆盖，如果下一个是空则说明已经到了尾部，插入这个结点，判断是否需要树化。

如果是覆盖已有的key，则会用新的value覆盖旧的value并返回旧的value。在遍历寻找是否存在这个key的过程中先判断hash值是否相等，如果相等，再进一步比较key是否equals，这里的equals方法可能被重写得较为复杂，因此先对hash进行判断可以减少equals的执行从而提高代码运行效率。先寻找有无相同key，若无再添加这个Entry并返回null。

hashmap.put(“1”, “2”)
String value = hashmap.put(“1”, “3”) // value = 2
String value = hashmap.put(“2”, “3”) // value = null, no overlap

为什么不直接用key做hash值而是与高16位做异或运算

异或可以使得高位也可以参与index的计算，使index更平均。

Hashtable 和 HashMap的区别

底层数据结构 (JDK1.8后不同)、父类不同 、扩容方法不同 、 线程上锁范围不同（重点）
hashtable：底层数组+链表实现，无论是key还是value都不能为null。线程安全，在修改时synchronize锁住了整个hashTable，效率低。
HashMap：底层数组+链表实现，可以存储null作为key或value，线程不安全。加载因子：为了降低哈希冲突，键值对达到数组内存75%的时候进行扩容，直接*2。
ConcurrentHashMap不支持key为null
HashTable容器使用sychronized来保证线程安全，采取锁住整个表结构来达到同步目的，在线程竞争激烈的情况下，当一个线程访问HashTable的同步方法，其他线程也访问同步方法时，会进入阻塞或轮询状态；如线程1使用put方法时，其他线程既不能使用put方法，也不能使用get方法，效率非常低下。

hashtable的理想的查找效率是多少？

哈希碰撞（在同一位置存放多个元素）怎么解决？

链表法：在数组中的entry的引用上加上一个next指针指向下一个元素。对于单链表来说，插入头部的速度时最快的。但是在查找过程中，单链表从数组中存放的entry开始只能向下查找，无法向上回溯，因此可能无法有效获取头插法插入的元素。解决方法：头插之后将链表向下移动，将插入的头元素作为链表放在数组中的那个元素。由于移动头节点相当于移动整个链表，只需将头节点放入数组：table[index] = new Entry(key, value, table[index])
探查法，双重散列（发生冲突之后以当前地址为基础找下一个地址直到没有冲突），双重哈希

参考：https://juejin.cn/post/6844904057128091655
https://www.cnblogs.com/sulishihupan/p/13418915.html