近几年HashMap是各大公司面试的热点，并由此延伸出非常多的东西，下面我们来讲解一些小知识点：
①HashMap的基本信息
②HashMap和HashTable的区别
③HashMap的底层实现
④HashMap解决碰撞问题
⑤ConcurrentHashMap的实现原理
?
一、HashMap的基本信息
? ? ? ?基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。?HashMap是无序的线程非安全的。
?
二、HashMap和HashTable的区别
? ? ? ?①HashMap是线程非安全的，HashTable是线程安全的。
? ? ? ?②HashMap可以接受null值和null键，HashTable不接受。
? ? ? ?③HashMap的迭代器是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
? ? ? ?④在单线程环境下，HashMap的速度比HashTable快，线程非安全的比线程安全的速度快，因为线程安全的存在一个加锁解锁的过程，当大量的这些过程累加到一块，是一个非常可观的时间。
? ? ? ?⑤HashMap不能保证随着时间的推移元素的次序不发生变化。
?
三、HashMap的底层实现：
? ? ? ?HashMap在1.8之前底层是由Entry?数组和链表组成，1.8是由Entry数组、链表和红黑树组成；先来讲一下1.8之前的底层实现；
?HashMap采用?Entry?数组来存储，每一个键值对组成一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，代码如下：
?
class="java"> static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
?1.8及之后加入了红黑树的概念，每当一个链表的长度大于8的时候，便自动转化为红黑树 ，结构如下图：
?
?HashMap按照key的hash值来计算Entry在HashMap中的储存位置的，当value值相同时候可以存在在不同的链表中去 ；
?
四、HashMap对HashCode碰撞的处理
? ? ? ?运用拉法来解决：HashCode是使用key通过hash函数计算出来的，由于不同的key，通过此函数可能会算出同样的HashCode，所以采用拉链法来解决冲突，把HashCode相同的?value连成链表，但是get的时候根据key又去桶里找，如果是在一个链表中说明是冲突的，此时还需要检测key是否相同；
? ? ? ?用拉链法解决问题的时候，在调用HashMap的put方法的时候，都会首先调用HashCode去查找相关的key，当有冲突的时候，在调用equals方法；
? ? ? ?当两个不同的键有相同的HashCode的时候，他们会存储在同一个?bucket位置的链表中，键对象的equals（）来找到对应的键值对；
?
五、?ConcurrentHashMap的实现原理
? ? ? ? ConcurrentHashMap是线程安全且高效的HashMap，在并发程序中使用HashMap可能导致程序死循环，而使用线程安全的HashTable效率又非常低下。
? ? ? ? HashMap在并发执行put操作的时候会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry；
? ? ? ?HashTable在多线程环境下，当一个线程访问HashTable的同步方法，其他线程也访问HashTable的时候，会进入阻塞或者轮询状态；
? ? ? ?ConcurrentHashMap是Segment数组结构和HashEntry数组结构构成，Segment是?一种可重入锁，在ConcurrentHashMap中扮演锁的角色，HashEntry则用于存储键值对数据：
结构图如下图所示：
?
ConcurrentHashMap使用?分段锁Segment来保护不同段的数据，每一把锁用于锁容器中的一部分数据，当多线程访问容器里面不同数据段的数据时，线程就不会存在锁竞争，，从而有效的提高并发访问效率。?
?
相关文章
