1. 什么是哈希表
哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表.
在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。
数据结构的物理存储结构只有顺序存储结构和链式存储结构，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
存储位置 = f(关键字)
其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。
2. HashMap实现原理
当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突.
哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式.
HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
key不保证映射的顺序，特别是它不保证该顺序恒久不变,key也不允许重复。key判断重复的标准是key1和key2是否equals为true,且hashcode是否相等.
注意点：
hashmap在jdk1.8后的改变：
https://blog.csdn.net/xingfei_work/article/details/79637878
https://www.cnblogs.com/stevenczp/p/7028071.html
https://www.cnblogs.com/zlslch/p/7622756.html
3. HashMap的put和get方法
① put方法
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，通过循环不断遍历链表查找是否在链表中有相同key的Entry
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//找到与插入的值的key和hash相同的Entry
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果发现已有该键值，则直接替换value值，并返回原始值, 跳出函数
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ，则需要新增Entry
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
②get方法
public V get(Object key) {
// 如果 key 是 null，调用 getForNullKey 取出null的 value
if (key == null)
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 直接取出 table 数组中指定索引处的值，
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null;
// 搜索该 Entry 链的下一个对象
e = e.next) {
Object k;
// 如果该 Entry 的 key和hash 与被搜索 key 相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
4. HashMap的resize
hashmap的内容越多, 冲突的几率也越高,所以为了提高查询的效率，就要对hashmap的数组进行扩容.
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为2 * 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适。
5. 重写equals方法需同时重写hashCode方法
- 如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同
- 如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面第一点
- 两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们"存放在同一个篮子里"
当不重写hashcode的时候, 会返回null尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时key(hashcode1)-->hash-->indexFor-->最终索引位置 ，而通过key取出value的时候key(hashcode2)-->hash-->indexFor-->最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null.
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
6.其他注意点:
- 在多个线程同时发现HashMap的大小过小时，都会尝试调整大小，会造成条件竞争。
- 在Java 8中，如果hash相同的key的数量大于8，会使用平衡树代替链表。
- 线程安全问题 :
①在两个线程同时尝试扩容HashMap时，可能将一个链表形成环形的链表，所有的next都不为空，进入死循环
②在两个线程同时进行put时可能造成一个线程数据的丢失
网友评论