HashMap、Hashtable和CurrentHashMap区别-Java基础

淡淡的烟草味﹌ 2022-01-12 09:47 244阅读 0赞

### **  1、HashTable** ###

**public** **synchronized** **boolean** contains(Object value) \{

**if** (value == **null**) \{

**throw** **new** NullPointerException();

Entry tab\[\] = table;

**for** (**int** i = tab.length ; i-- > 0 ;) \{

**for** (Entry<K,V> e = tab\[i\] ; e != **null** ; e = e.next) \{

**if** (e.value.equals(value)) \{

**return** **true**;

**return** **false**;

1.  value值是不允许为null;
2.  方法同步的，线程安全；D.其方法几乎都是同步的。
3.  Key == null会抛出空指针异常；
4.  初始大小为11.Hashtable的扩容是原来容量的二倍加1（2n+1）。
5.  继承自Dictioonary类；
6.  计算hash值的方法：

**public** **synchronized** **int** hashCode() \{

**int** h = 0;

**if** (count == 0 || loadFactor < 0)

**return** h;  // Returns zero

loadFactor = -loadFactor;  // Mark hashCode computation in progress

Entry\[\] tab = table;

**for** (**int** i = 0; i < tab.length; i++)

**for** (Entry e = tab\[i\]; e != **null**; e = e.next)

h += e.key.hashCode() ^ e.value.hashCode();

loadFactor = -loadFactor;  // Mark hashCode computation complete

**return** h;

7. 是线程安全，所以不采取快速迭代机制；效率低，在修改数据时锁住整个hashtable.

### **2、HashMap** ###

底层存储是哈希表（数组+链表）。

**public** V get(Object key) \{

**if** (key == **null**)

**return** getForNullKey();

**int** hash = *hash*(key.hashCode());

**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.equals(k)))

**return** e.value;

**return** **null**;

1.  key可以为空值；

**public** **boolean** containsValue(Object value) \{

**if** (value == **null**)

**return** containsNullValue();

Entry\[\] tab = table;

**for** (**int** i = 0; i < tab.length ; i++)

**for** (Entry e = tab\[i\] ; e != **null** ; e = e.next)

**if** (value.equals(e.value))

**return** **true**;

**return** **false**;

1.  value可以为null；value可以重复；
2.  线程不安全，无synchronized修饰，非线程安全；

**void** resize(**int** newCapacity) \{

Entry\[\] oldTable = table;

**int** oldCapacity = oldTable.length;

**if** (oldCapacity == *MAXIMUM\_CAPACITY*) \{

threshold = Integer.*MAX\_VALUE*;

**return**;

Entry\[\] newTable = **new** Entry\[newCapacity\];

transfer(newTable);

table = newTable;

threshold = (**int**)(newCapacity \* loadFactor);

1.  初始大小为16.Reaize()方法，当容量不够的时候进行扩充。达到最大的时候则不扩充。当不是最大的时候，容量会变为原来的二倍，并且阈值也会发生变化，变为原来阈值的二倍。扩充是再堆里重新创建新的HashMap容器，然后把原来的元素放在新容器中。其size一定为2的n次幂。
2.  继承了AbstractMap类;
3.  允许为null，所以判断是都存在某个键，不是get()而是containsKey()方法进行判断。
4.  线程不安全，如果想使得线程安全，Collections.synchronizedMap(hashMap)来进行处理，或者用线程安全的ConcurrentHashMap。
5.  计算hash的值：

**public** **final** **int** hashCode() \{

**return** (key==**null**   ? 0 : key.hashCode()) ^

(value==**null** ? 0 : value.hashCode());

1.  由所有HashMap类的”collection视图方法”所返回的迭代器都是快速失败的，如果在使用迭代器的过程中有其他线程修改了集合对象结构或者元素数量，就会抛出ConcurrentModificationException这就是fail-fast策略，也就是快速迭代机制。

1.  寻址方式:将key的哈希值对数组长度进行取模，结果作为该Entry在数组中的index。
2.  HashMap不允许通过Iterator遍历的同时通过HashMap修改；

1.  在jdk8不超过8个用链表存储，超过8个会调用treeifyBin函数，将链表转换为红黑树。即使key相同查找某个特定元素，也只需要O(log n)的开销。

### **3、CurrentHashMap-java8** ###

A. JDK1.7之前采用分段锁结构，采用锁分离实现多线程安全,采用segment，其继承ReentrantLock，因此采用Lock锁来保证线程安全。JDK1.8之后采取数组+链表+红黑树,通过CAS+Synchronized保证线程安全。

B. 线程安全，key和value不允许为null。

C. 允许通过Iterator遍历的同时通过HashMap修改；

**什么是红黑树**

1）每个节点要么是红要么是黑

2）根节点是黑

3）每个叶节点都是黑（叶节点指树尾端NIL或null节点）

4） 如果一个节点是红的，子节点就是黑的

5）对于任意节点，其到叶节点尾端的每条路径都包含相同数目的黑节点。(所以是接近平衡的二叉树)

**JDK1.8ConcurrentHashMap的数据结构已经接近HashMap**

1.  JDK1.8降低锁的粒度。之前锁的粒度为多个HashEntry，之后就是首节点HashEntry。
2.  结构更简单，操作更方便，使用synchronized进行同步，不需要分段锁。
3.  红黑树优惠链表，遍历效率提高；

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190621101406596.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70 1]: /images/20220109/5088c86ff9464dc3ba408df3ae10724d.png