HashTable和HashMap很神奇诶！看了很多大佬的博客，想自己简单整理一下。
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);
for(Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
这段代码涉及到HashMap的声明和简单的put方法，最后输出的时候用Entry结构进行遍历，这个结构后面也会提到
代码最终的运行结果为
政治: 5
生物: 7
历史: 4
数学: 2
化学: 8
语文: 1
英语: 3
地理: 6
HashMap是如何存储的呢？如下图所示
HashMap插入的结果
对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。 也就是说，每个桶bucket的位置上存放的是一个Entry或者Entry链。
那么Entry是什么？Entry数组的大小，即capacity为多少？Entry链如何形成的？
Entry
HashMap和HashTable都使用哈希表来存储键值对。在数据结构上是基本相同的，都创建了一个继承自Map.Entry的私有的内部类Entry，每一个Entry对象表示存储在哈希表中的一个键值对。
Entry对象唯一表示一个键值对，有四个属性：
-K key 键对象
-V value 值对象
-int hash 键对象的hash值
-Entry next 指向链表中下一个Entry对象，可为null，表示当前Entry对象在链表尾部
可以说，有多少个键值对，就有多少个Entry对象
Entry数组
与Entry数组大小相关的参数有四个，一是capacity，二是load factor，三是threshold，四是size
Entry数组的initialCapacity（初始化容量）以及load factor(负载因子必须大于0)
Entry数组的capacity大小 = 找出大于 initialCapacity 的、最小的 2 的 n 次方值，比如initialCapacity = 10，则设置capacity = 16 ，而load factor决定了整个bucket填充的数目，即hashmap元素的个数，当bucket填充的数目大于 capcity*load fator时，HashMap 会自动调用 resize 方法扩充 HashMap 的容量。每扩充一次，HashMap 的容量就增大一倍
其中，capacity*load factor = threshold，size用来在程序记录当前hashmap内包含的key-value数目
HashMap put操作
从代码中可以看到几点：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
- HashMap支持null key 和null value，这也是HashMap和HashTable的一个不同；当key为NULl时，HashTable会抛出异常
hashCode()和hash：每个java对象都有一个hashCode()，通过调用这个构造方法，即可获得对象的hashCode，hash函数是对 对象 的 hashCode进行处理，然后得到对应的hash值；
计算hash值的index会调用函数indexFor(int h, int length)
当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部(具体操作在AddEntry中进行)
HashMap get操作
- bucket里的第一个节点，直接命中；
- 如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)
Hash操作
可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或
Hash操作
此处我们需要区别几个概念：
equals：是否同一个对象实例。注意，是“实例”。比如String s = new String("test"); s.equals(s), 这就是同一个对象实例的比较；
等号(==)：对比对象实例的内存地址（也即对象实例的ID），来判断是否是同一对象实例；又可以说是判断对象实例是否物理相等；
HashCode：我觉得可以这样理解：并不是对象的内存地址，而是利用hash算法，对对象实例的一种描述符（或者说对象存储位置的hash算法映射）——对象实例的哈希码。
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。
重新调整HashMap会产生问题
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。
尾部遍历问题
尾部遍历问题是防止在插入过程中的效率低效的问题，所谓的尾部遍历，就是对于队列而言，插入新的元素时，如果插入到队列的尾部，需要遍历整个队列找到尾部=>这样的做法效率低下；为了防止尾部遍历，可以直接在队头插入，这也是HashMap AddEntry的做法
死循环问题
HashMap是线程不安全的，当多线程操作时，尤其在resize过程中，会出现死循环问题，想说明白这个问题，就需要看一下源代码了
HashMap的put操作
public V put(K key, V value)
{
......
//算Hash值
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//如果该key已被插入，则替换掉旧的value （链接操作）
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;
}
}
modCount++;
//该key不存在，需要增加一个结点
addEntry(hash, key, value, i);
return null;
}
检查容量是否超标
void addEntry(int hash, K key, V value, int bucketIndex)
{
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
if (size++ >= threshold)
resize(2 * table.length);
}
新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
//创建一个新的Hash Table
Entry[] newTable = new Entry[newCapacity];
//将Old Hash Table上的数据迁移到New Hash Table上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
迁移代码
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
//下面这段代码的意思是：
// 从OldTable里摘一个元素出来，然后放到NewTable中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
看了这么多，终于到重点问题了！从代码中可以看出，HashMap的扩容问题，其实就是重新遍历一遍旧的Entry数组，依据e和next依次将Entry插入新的HashMap中，当然，为了避免尾部遍历问题，都是直接插入头部
正常的ReHash过程
正常的单线程的ReHash
并发下的rehash过程
假设有两个线程，每个线程都是在自己的栈中处理旧的HashMap，然后将处理后的结果写入内存更新
线程一被挂起，执行线程二
线程一的e指向key=3，next指向key=7，这些信息都在线程一自己的栈中，此时线程一被挂起，执行线程二；线程二执行完成后，原有的旧的HashMap被更新
线程一获得资源
线程一重新获得资源开始执行，由于之前e是key=3，next是key=7，此时先处理key=3，然后e变成7，但是由于线程二更新了HashMap，key=7的next变成了key=3，此时，e指向key=7，next指向key=3；
处理key=7以后，继续处理key=3（注意⚠️，现在的Entry链中，key=7的next就是key=3，此时再去处理e:key=3，出现的问题就是，key=3的next会指向key=7，key=7的next会指向key=3，出现循环♻️）
死循环
总结
1. 什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
2. 你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
4. 你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
6. HashTable和HashMap有什么不同
（1）HashMap是支持null键和null值的，而HashTable在遇到null时，会抛出NullPointerException异常。这并不是因为HashTable有什么特殊的实现层面的原因导致不能支持null键和null值，这仅仅是因为HashMap在实现时对null做了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket中。
（2）HashTable是同步的，HashMap不是，也就是说HashTable在多线程使用的情况下，不需要做额外的同步，而HashMap则不行。
7. 为什么说HashMap是线程不安全的
在Resize的过程中，如果是多线程的，则会造成资源竞争，造成死循环问题
参考
1.https://stackoverflow.com/questions/22890967/java-hashmap-tail-traversing
2.http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
3.http://www.importnew.com/7099.html
4.http://alex09.iteye.com/blog/539545
5.https://coolshell.cn/articles/9606.html
6.https://blog.csdn.net/zhuqiuhui/article/details/51849692
7.http://www.importnew.com/24822.html
网友评论