前言
RTFSC (Read the fucking source code )才是生活中最重要的。我们天天就是要读懂别人的，理解别人的，然后再模仿别人的，最后才是创新自己的。人生大半的时间是在学习，所以我们一定要RTFSC
对比
| 名称 | 线程是否安全 | key是否可为空 | value是否可为空 | key是否可以重复 | value是否可以重复 |
|---|---|---|---|---|---|
| HashMap | 否 | 是 | 是 | 否 | 是 |
| Hashtable | 是 | 否 | 否 | 否 | 是 |
注：理解以下代码，需要事先明白一个道理，不同的key,hash值不一定不同。相同的key，hash值一定相同。
HashMap
之前转载过一篇《图解HashMap》。HashMap就是基于哈希表的 Map 接口的实现的类。是我们开发中常用的一种数据结构，以键值对的方式存取数据。HashMap从语文角度来看可以说是一个偏正短语,Hash即为散列(也叫哈希)算法。Map就是Key-Value的方式存储数据的一种数据结构。HashMap实例化时其两个参数会影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
接下来一步一步对源码进行分析，彻底掌握HashMap的特性。
transient Node<K,V>[] table;
HashMap中的数据保存在table数组中，每一个数据又是一个Node实例，这里可以去看一下Node源码保存了哪些信息。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//初始化Node实例
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;
}
}
代码比较简单，主要看初始化的地方，保存了hash值，此值就是key值通过哈希算法算出来的值，然后是key和value信息。还有一个Node节点next，这里也可以看出HashMap中存在链表。在发生哈希碰撞的时候，数据会链接在链尾。
HashMap中保存的数据大概图例：
图片.png
再来看一下我们常用的put,get方法。
put(key,value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
会调用putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过key的hash值与table长度得到index位置的p节点对象，如果为空，数据存放在当前位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//p不为空，当前位置存在数据，如果key相同，会把p赋值给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//走到此处代表发生了hash碰撞，需要将新的node节点接在p节点为首的尾链。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//此处得到之前的e，把新的value赋值给原来的位置，覆盖之前的value，并返回之前的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get(key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
调用getNode(hash,key)方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//此处还是通过hash值与table.length得到存放数据的位置，得到节点first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断first的hash与key是否与需要获取value的hash，key相同
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//走到这里，需要在当前节点为首的链表循环，找到hash与key都相同的节点
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Hashtable
Hashtable的实现在思路上是和HashMap差不多的。我们直接看put方法
put(key,value)
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//此处还是通过hash与table.length计算出index位置。
@SuppressWarnings("unchecked")
HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
//循环查找是否存在key重复的数据，存在就覆盖，并返回老数据的value。
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//entry为空，index位置添加数据
addEntry(hash, key, value, index);
return null;
}
addEntry(hash,key,value,index)方法：
private void addEntry(int hash, K key, V value, int index) {
modCount++;
HashtableEntry<?,?> tab[] = table;
//数据量超过指定阈值时，需要重新分配一次大小，并且重新计算index
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//然后在index位置加入数据
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
tab[index] = new HashtableEntry<>(hash, key, value, e);
count++;
}
get(key)方法：
public synchronized V get(Object key) {
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//还是计算出index，以此节点为头，遍历链表找出指定节点，返回value值即可
for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
总结
HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有：线程安全性与可接受的值。
- HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。
- HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
- 由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
- HashMap不能保证随着时间的推移Map中的元素次序是不变的。
个人理解，如有错误请指出~
转载请注明出处
https://www.jianshu.com/p/3f89c53f52ac
