HashMap的底层实现原理，get的过程发生了什么
HashMap是用来存储key-value键值对的集合，每一个键值对叫做一个Entry，这些Entry分散存储在一个数组之中，这个数组就是HashMap的主干。
get方法：
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get方法通过key值返回对应的value，如果key为null，直接去table[0]处检索。
getEntry方法：
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)] ; e != null ; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
key(hashcode)-->hash-->indexFor-->最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。
-
hashcode方法：当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。
-
不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等，但是可以直接根据hashcode值判断两个对象不等，如果两个对象的hashcode值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过equals方法。
就是说对于两个对象，如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；
如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；
如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；
如果两个对象的hashcode值相等，则equals方法得到的结果未知。 -
重写equals()方法的同时也要重写hashCode()方法：
hashCode方法默认将对象的存储地址进行映射。所以，如果重写了equals()方法，同时要重写hashCode()方法。 -
Hash方法的规定：
1.在 Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
2.如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
3.如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不 要求一定生成不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同整数结果可以提高哈希表的性能。
假设两个对象，重写了其equals方法，其相等条件是属性相等，就返回true。如果不重写hashcode方法，其返回的依然是两个对象的内存地址值，必然不相等。这就出现了equals方法相等，但是hashcode不相等的情况。这不符合hashcode的规则。
参与equals函数的字段，也必须都参与hashCode 的计算
package com.cxh.test1;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
class People{
private String name;
private int age;
public People(String name,int age) {
this.name = name;
this.age = age;
}
public void setAge(int age){
this.age = age;
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return name.hashCode()*37+age;
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;
}
}
public class Main {
public static void main(String[] args) {
People p1 = new People("Jack", 12);
System.out.println(p1.hashCode());
HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
hashMap.put(p1, 1);
System.out.println(hashMap.get(new People("Jack", 12)));
}
}
输出为1。
- 在程序执行期间，只要equals方法的比较操作用到的信息没有被修改，那么对这同一个对象调用多次，hashCode方法必须始终如一地返回同一个整数。
- 如果两个对象根据equals方法比较是相等的，那么调用两个对象的hashCode方法必须返回相同的整数结果。
- 如果两个对象根据equals方法比较是不等的，则hashCode方法不一定得返回不同的整数。
- 设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该产生同样的值。如果在讲一个对象用put()添加进HashMap时产生一个hashCdoe值，而用get()取出时却产生了另一个hashCode值，那么就无法获取该对象了。所以如果你的hashCode方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，hashCode()方法就会生成一个不同的散列码。
HashMap与Hashtable的区别
1、Hashtable线程安全，速度较慢。它为每一个方法都加了Synchronize方法。在多线程环境下，可以直接使用Hashtable。HashMap不是线程安全的，速度较快，在使用时可能会产生死锁问题。在多线程环境下使用要自己加入同步方法。
2、计算hash值的方法不同。
Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。
hashtable计算hash方法
Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。
HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高。
为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2 的幂次方带来的效率提升给抵消掉。
hashmap计算hash方法
3、Hashtable中，key与value都不允许出现null。在 HashMap 中， null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null 。当 get() 方法返回 null 值时，即可以表示 HashMap 中没有该键，也可以表示该键所对应的值为 null 。因此，在 HashMap 中不能由 get() 方法来判断 HashMap 中是否存在某个键， 而应该用 containsKey() 方法来判断。
HashMap能否实现同步
可以，可以使用ConcurrentHashMap，或者
Map m = Collections.synchronizeMap(hashMap);
API
HashMap实现原理
- JDK1.8之前：数组+链表
- JDK1.8及之后：数组+链表，当链表长度大于阈值（默认为8）时，将链表转变为红黑树，以减少搜索时间。TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
java7中 hashMap每个桶中放置的是链表，这样当hash碰撞严重时，会导致个别位置链表长度过长，从而影响性能。
java8中，HashMap 每个桶中当链表长度超过8之后，会将链表转换成红黑树，从而提升增删改查的速度。
详细内容参照 GitHub
ConcurrentHashMap与HashTable的区别
主要体现在实现线程安全的方式的不同
- 底层数据结构不同：1.7之前的ConcurrentHashMap使用的是数组加链表，1.8之后的ConcurrentHashMap使用的和1.8的HashMap一样，在阈值大于8时，转化为红黑树。
- 实现线程安全的方式不同：
HashTable（同一把锁）：使用 synchronized来保证线程安全，效率很低，当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
ConcurrentHashMap ：1.7的时候，使用分段锁，对整个桶数组进行分割分段（Segment）,每一把锁只锁容器其中一部分数据。多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
到了1.8的时候，已经摒弃了segment的概念，直接用Node数组+链表+红黑树的数据结构来实现，并发使用synchronized和CAS来操作。整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。
详细内容参照 GitHub
高并发下HashMap容易出现的问题
多线程并发扩容的时候容易发生死循环。
HashMap并不是线程安全，所以在多线程情况下，应该首先考虑用ConcurrentHashMap。
在高并发的情况下，是非常可能发生死循环的，由此造成CPU 100%，这是非常可怕的。
原因简单来说：如果HashMap到达临界容量需要扩容，两个线程同时进行resize操作，同时开辟两块空间，线程挂起时机不当时，rehash会产生环路。
多线程HashMap
当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好等于3的时候，由于位置3带有环形链表，所以程序将会进入死循环！
为什么数组长度要保证为2的幂次方？
在确定哈希桶数组索引位置的时候，有一步操作是用元素的hash值与HashMap的长度-1 做“与”运算，对于新插入的数据或者待读取的数据，HashMap将Key的哈希值对数组长度取模，结果作为该Entry在数组中的index。在计算机中，取模的代价远高于位操作的代价，因此HashMap要求数组的长度必须为2的N次方。
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
当数组长度为2的幂次的时候，h&(length-1)才等价于h%length，即实现了key的定位，2的幂次方也可以减少冲突次数，提高HashMap的查询效率；
如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式，在与 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length - 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。
一招破解 Java 集合类面试题
ConcurrentHashMap在JDK1.7和JDK1.8中的实现
Java7中的ConcurrentHashMap的底层数据结构仍为数组+链表，但与HashMap不同的是， ConcurrentHashMap最外层不是大数组，而是一个Segment数组，每个segment数组包含于HashMap数据结构差不多的链表数组。整体数据结构如下：
寻址方式：
在读写某个key时，先取该key的hash值，并将哈希值的高N位对Segment个数取模从而得到该key应该属于哪个Segment，接着如同操作HashMap一样操作Segment。
同步方式：
Segment继承自ReentrantLock，是一种可重入锁，所以我们可以很方便的对每一个Segment上锁。
对于读操作，获取Key所在的Segment时，需要保证可见性。具体实现上可以使用volatile关键字，也可使用锁。但使用锁开销太大，而使用volatile时每次写操作都会让所有CPU内缓存无效，也有一定开销。ConcurrentHashMap使用如下方法保证可见性，取得最新的Segment。
Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)对于写操作：并不要求在写的时候把所有的Segment都锁住，那样相当于锁住了整个map，它会先获取这个key对应的Segment的锁，获取成功后就可以像操作普通HashMap一样操作该Segment，并保证Segment的安全性，同时其他的Segment并没有被锁住，因此理论上可以支持Segment个数的线程同时安全的并发读写。
获取锁时，并不直接使用lock获取，因为该方法在失败的时候会挂起，事实上，他是用了自旋锁，如果trylock失败，就会通过循环再次尝试trylock，如果次数超过一定限制，就转化为lock互斥锁。
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁
以上仅针对Java7有效
在Java8中，为进一步提高并发性，摒弃了Segment的概念，和HashMap一样，在链表长度小于阈值的时候，使用数组+链表，超过阈值之后，转化为红黑树。
同步方式：put操作，如果key对应的数组元素为null，则通过CAS将其设置为当前值，如果key对应的数组元素（链表表头或者树根）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作，如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。
对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例（Java 7中每个元素是一个HashEntry），它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障。
size操作：
put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。
散列表处理hash冲突的方法
- 开放定址法
ThreadLocalMap
如果发生冲突，算法会简单的从该槽位置向后循环遍历hash表，直到找到表中的下一个空槽，并将该元素放入该槽中（会导致相同hash值的元素挨在一起和其他hash值对应的槽被占用） - 链地址法
hashmap
拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。 - 再散列法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
网友评论