面试问题：HashMap的实现？
参考：https://segmentfault.com/a/1190000012926722
参考：极客时间 散列表部分。
查找，删除，插入都快，key和value都能为空，key会覆盖，value能重复，遍历时和插入顺序不一致。
========================================================
首先hsahmap是一个散列表，散列表的优势是在O(1)的时间内实现对数据的增删改查，其最根本的原理是基于数组可以通过下标在O(1)的时间内实现对数据的访问，散列表则是通过散列函数算出数组的下标，从而达到效率最优。
一个工业级别的散列表还需要考虑：1.合适的散列函数。2.解决散列冲突的方案。3.合适的装载因子阈值和动态扩容策略。
========================================================
1.合适的散列函数：散列函数的目的是算出key对应的桶数组下标，java8将其拆分成了两步，首先通过hash（）重新计算一次hash。然后做&操作计算下标。
hash值的计算是，取出key的hashCode和将hashCode 的低位和高位做一次亦或运算得到，如:(key.hashCode()) ^ (h >>> 16)。
在hash（）函数中，为啥没直接用类自己的hashCode（）方法？
首先在计算一个key所在桶的位置的方式是：index=hsah&(size-1)。
key的散列值=(key.hashCode()) ^ (h >>> 16),之所以没有直接使用hsahCode()是为了避免当hash表的size太小时，做&操作时，hash值只有低位参与运算，所以需要让32位的原hash值右移16位，取出高16位参与运算。这样可以增强hash值的随机性，同时也防止了自定义的hashCode方法算出的hashCode分布不均匀的情况。
=================
计算一个元素的桶在通数组中的位置，或者为啥能通过&而不是%的方式计算桶的位置？
理论上:index=散列值hash%桶数组size。 由于桶数组的大小总是2的n次幂(size：1000000.....，size-1:0111111.....)，对hash求模可以视为向右移动n位后，被移出去的那几位组成的数，也就是size-1中1对应的那几位数字，所以%运算可以优化成：index=hsah&(size-1)。
*为了能够使用&操作快速算出桶的位置，桶数组的大小必须是2的n次幂。
TODO:如何保证桶数组的大小总是2的n次幂？
========================================================
2.散列冲突解决方案
散列函数存在 key不同但是散列算出的地址相同的情况，称为散列冲突。
解决散列冲突的方式：开放寻址法和链表法。 开放寻址法就是按照一定的规则再找一个位置存放key，链表法是在冲突的位置上建立一个链表，每当出现一个冲突的key,就将元素加入链表。LinkedHashMap采用链表法，ThreadLocalMap通过开放寻址法解决冲突。
散列冲突最根本的原因是用来存放key值的数组空间太小了，所以需要保证一定的空闲槽位降低冲突的概率。装载因子就是用来衡量数组空闲槽位的。
装载因子=数组元素个数/数组总长度。
3.合适的装载因子和动态扩容策略。
为了计算桶位置时可以使用&操作以及扩容时可以减少rehash步骤，桶数组的真正大小总是2的n次幂。
扩容时，首先判断是否是初始化，如果初始化，按照指定的容量和加载因子指定桶数组大小，和扩容阈值。如果不是初始化，桶数组和扩容阈值增长到原来的2倍。将原桶数组的数据搬移到新的桶数组中，如果一个桶上的数据是链表的话，会拆成两条链表同时重新计算桶的下标。(元素所在桶的位置计算规则是:如果key的hash值&旧容量=0则下标不变，如果!=0,下标+旧容量的值。) ；如果原桶数据是一颗红黑树，则拆分成两颗红黑树原index和index+oldCap，如果元素数量少于6，则退化成链表。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//进行扩容时，先得知道原桶数组的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//threshold是原桶数组的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果不是初始化
if (oldCap >= MAXIMUM_CAPACITY) {
//当原桶数组size>=(int最大值的一半)，只是将阈值设到最大，不再扩容。
threshold = Integer.MAX_VALUE;
return oldTab;
}
//将容量和阈值设置为原来的2倍。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果是初始化，且指定了初始容量，根据tableSizeFor(initialCapacity)确定
//桶数组大小，阈值在下面的操作中指定。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果是初始化,且没有指定初始化容量，使用默认的桶数组大小和阈值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果上面没有指定阈值大小，将阈值大小设置为容量*装载因子
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//根据容量创建新的桶数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//原本在搬移数据时，需要对每一个元素进行rehash的，但是这
//里根据如下规律做了优化：hash&oldCap=0的新旧hash值相等
// hash&oldCap!=0 新hash=旧hash+oldCap
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
=======================
========================================================
HashMap 的遍历,应用于Map转ArrayList:new ArrayList<>(deliveryItemModelMap.values());
abstract class HashIterator {
HashMap.Node<K,V> next; // next entry to return
HashMap.Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
HashMap.Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final HashMap.Node<K,V> nextNode() {
HashMap.Node<K,V>[] t;
HashMap.Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
/**
* 这段代码的意思是：从哈希表的第一个桶开始，找链表下一个元素，如果下一个元素为空，则换到哈希表的下一个桶
*/
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
HashMap.Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
========================================================
4.如何实现遍历？为何遍历顺序和插入顺序不一致呢？
首先，foreach keySet 等价于:Set set=map.keySet(); Iterator it=set.iterator(); while(it.hasNext()){Object key=it.next();}。
set.iterator()会new一个迭代器，同时从0开始向后找，定位到第一个非空的桶，核心逻辑在HashIterator 中。在while中不断调用nextNode时，首先遍历完当前桶的链表，然后再找到下一个桶的链表(或者红黑树)。之所以和插入顺序不同，是因为
首先插入不会按照从0-n的顺序计算桶，其次，每次插入只有在key的hash值相等时才会一直像遍历那样向一个桶的链表中插入数据。
========================================================
4.扩展：散列表+链表实现LRU算法。LinkedHashMap的实现原理。
LinkedHashMap会按照put 和get的顺序遍历元素。
hash 和链表（跳表）的结合在补足了散列表不能排序的补足。
=======================================
===================================================
LinkedHashMap的源码参考：
https://www.jianshu.com/p/8f4f58b4b8ab
https://www.cnblogs.com/xrq730/p/5052323.html
===================================================
SortedMap->TreeMap,
HashMap,
WeakHashMap,
EnumMap,两个数组，一个是key[],val[]。通过枚举类型的ordinal()获取序号，取val下标。
HashTable->Properties:hash方式： (key.hashCod() & 0x7FFFFFFF) % tab.length算出索引位置，hash冲突：只会拉一个链表，扩容：达到装载因子（默认0.75f）阈值，原容量*2+1。参考：https://blog.csdn.net/shennongzhaizhu/article/details/51871014
IdentityHashMap:如名字一样，这是一个特殊的hashmap,使用==而不是equals判断key是否相等，使用System.identityHashCode 根据对象的内存地址计算hash值，也是通过&算出index的，hash冲突，紧接着在后面找一个位置（i放key,i+1放value,删除时需要把后面的搬移到前面去），达到1/3进行扩容扩为原来的2倍。
参考：https://www.jianshu.com/p/1b441546078a
参考博客：https://www.cnblogs.com/skywang12345/p/3311092.html
问题：WeakHashMap和HashMap有哪些异同点？
1.设计目标：两者都扩展了AbstractMap,实现Map接口但HashMap还实现了clone和serializable。这充分说明了两者的应用场景：前者只会涉及到内存的操作，后者的应用场景更加广泛。（问题1：clone和serializable都用在什么情况下？
问题2：如何实现深度copy？
问题3：具体谈谈WeakHashMap为啥没有实现clone,serializable接口？
）,两者在数学意义上的hash算法，扩容策略都一样，都是链表法解决hash冲突，但hashmap多做了许多优化(多了一次hash,引入红黑树，算初始容量使用位操作，数据搬移时链表直接拆成两条，而不是rehash)。
-
初始化：WeakHashMap在初始化阶段申请数组空间，HashMap在第一次put时申请数组空间，数组初始长度都是小于等于指定容量的2的n次幂(但是算法不一样)。两者的装载因子阈值都是0.75f,初始数组上限都是2的30次幂。
3.数据结构：两者的hash表都保存的是键值对节点。节点对象都实现了Map.Entry接口，WeakHashMap还继承了WeakReference类。这是WeakHashMap得以实现的核心，HashMap持有的对象不会被垃圾回收掉，但WeakReference持有的对象在没有被其他地方引用时，可以被垃圾回收掉，当调用WeakHashMap的方法时，WeakHashMap会调用expungeStaleEntries()检查那些被回收掉的对象，并删除对应的节点。private void expungeStaleEntries() {
//gc线程会把回收后的弱引用放入queue中，方便删除失效的节点。
for (Object x; (x = queue.poll()) != null; ) {
//删除失效节点时需要保持同步
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;
//首先通过hash找到数组下标
int i = indexFor(e.hash, table.length);
//因为是单向链表，定义两个指针，一个指向前驱，一个指向当前，方便删除。
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
//如果找到节点
if (p == e) {
//如果删除的是头节点，将next节点顶上来
if (prev == e)
table[i] = next;
else
//如果不是头节点，把当前节点拆除
prev.next = next;
//手工置成null帮助gc。
e.value = null; // Help GC
//size作为成员变量，记录的是hash表中元素的个数
size--;
//删除成功，直接退出即可
break;
}
//如果没有找到匹配节点就继续向后滑动指针。
prev = p;
p = next;
}
}
}
}
put操作时，首先查找是否存在key相同的节点，然后替换掉；然后创建一个新节点放入桶中，原节点则作为next传入新节点中。换句话说，新节点总是在表头插入的。这样无论是hash冲突还是插入新节点都是相同的逻辑，很好的简化了代码。
网友评论