从源代码角度来分析HashMap、HashTable、TreeMap的区别

港控/mmm° 2022-11-07 14:39 109阅读 0赞

### 目录 ###

*   *  一、HashMap
     *   *  1、结论
         *  2、证明
         *   *  2.1、HashMap是Map接口的实现类
             *  2.2、底层数据结构是哈希表
             *  2.3、不是线程安全的
             *  2.4、默认初始化容量是16，默认加载因子是0.75，默认在链表尾部添加节点，按照原来的两倍大小进行扩容；当哈希表的长度大于等于64，并且某条链表长度大于等于8，那么会将这条链表变成红黑树，另外hash算法不同
             *  2.5、键和值都可以是null
             *  2.6、如果设置HashMap的初始化容量，但是初始化容量不是2的幂次方，那么会将该容量变成2的幂次方
             *  2.7、get(Object key)方法
             *  2.8、remove(Object key)方法
     *  二、HashTable
     *   *  1、结论
         *  2、证明
         *   *  2.1、HashTable是Map接口的实现类
             *  2.2、底层数据结构是哈希表
             *  2.3、是线程安全的
             *  2.4、默认初始化容量是11，默认加载因子是0.75，默认在链表头部添加节点，按照原来的两倍大小+1进行扩容，键和值都不能是null
             *  2.5、键和值都不能是null
             *  2.6、get(Object key)
             *  2.7、remove(Object key)
     *  三、TreeMap
     *   *  1、结论
         *  2、证明
         *   *  2.1、TreeMap是Map接口的间接实现类
             *  2.2、底层数据结构是红黑树
             *  2.3、不是线程安全的
             *  2.4、根据key进行排序
     *  四、类图

## 一、HashMap ##

### 1、结论 ###

HashMap是Map接口的实现类，底层数据结构是哈希表，不是线程安全的，默认初始化容量是16，默认加载因子是0.75，默认在链表尾部添加节点，按照原来的两倍大小进行扩容，键和值都可以是null；如果设置HashMap的初始化容量，但是初始化容量不是2的幂次方，那么程序会将该容量变成2的幂次方；当哈希表的长度大于等于64，并且某条链表长度大于等于8，那么会将这条链表变成红黑树，另外hash算法不同

### 2、证明 ###

注意：以下代码来自于HashMap类的源码；

#### 2.1、HashMap是Map接口的实现类 ####

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable

#### 2.2、底层数据结构是哈希表 ####

transient Node<K,V>[] table;

#### 2.3、不是线程安全的 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70]

#### 2.4、默认初始化容量是16，默认加载因子是0.75，默认在链表尾部添加节点，按照原来的两倍大小进行扩容；当哈希表的长度大于等于64，并且某条链表长度大于等于8，那么会将这条链表变成红黑树，另外hash算法不同 ####

// 加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */
    public HashMap() { 
    	// 加载因子默认就是0.75
    	this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

在上面注释中已经说的很清楚了，但是代码在`resize()`方法中，如果想要分析该方法，那我们还需要分析put方法，另外趁着这个机会我们好好分析一下里面的方法！

注意：以下分析主要建立在使用默认无参构造方法，然后初次添加和中间添加键值的情况都会涉及到
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 这个值是1073741824
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    static final int TREEIFY_THRESHOLD = 8;
    
    transient Node<K,V>[] table;
    
    // 存储元素
    public V put(K key, V value) { 
    	// 真正执行存储元素的方法，里面有个hash算法，我们下面会解释
    	return putVal(hash(key), key, value, false, true);
    }
    
    // hash算法
    static final int hash(Object key) { 
    	int h;
    	// key == null的结果是0，所以HashMap中的key可以是null，这是一种hash算法，
    	// 而HashTable中是直接调用hashCode()方法得出hash值，然后在通过运算得到对应的索引值，所以两种结构的hash算法是不同的
    	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    // 真正存储元素的方法
    // 对于onlyIfAbsent，官方注释是：if true, don't change existing value，本次是false，那就是会改变已经存在的值，代码中也确实用到了，等用到的时候在详细解释；
    // 对于evict，官方解释是：evict if false, the table is in creation mode，本次是true，然后可能会根据LRU算法删除比较老的元素，但是由于代码原因，所以不会删除值；
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    			   boolean evict) { 
    	Node<K,V>[] tab; Node<K,V> p; int n, i;
    	// 初次：table是null，所以tab是null，因此结果为true，那后半部分就不用看了
    	// 中间：table不是null，所以tab不是null，因此前半部分是false，后半部分也是false，所以最终结果是false
    	if ((tab = table) == null || (n = tab.length) == 0)
    		// 初次：resize()方法会调整哈希表大小为16，所以n是16
    		n = (tab = resize()).length;
    	// 初次：(n - 1) & hash是15 & 16，结果是0，那么p就是哈希表中索引为0的值，正好就是null，所以结果是true
    	// 中间：p可能不是null，所以结果可能就是false，不过也可能是null，毕竟不是每一个位置都有值
    	if ((p = tab[i = (n - 1) & hash]) == null)
    		// 初次：将节点直接放在哈希表中
    		// 中间：将节点直接放在哈希表中
    		tab[i] = newNode(hash, key, value, null);
    	else { 
    		Node<K,V> e; K k;
    		// 中间：如果链表中第一个节点就是该节点，说明本次执行的是更新操作
    		if (p.hash == hash &&
    			((k = p.key) == key || (key != null && key.equals(k))))
    			// 中间：e是链表中的第一个节点
    			e = p;
    		else if (p instanceof TreeNode)
    			// 中间：如果不是普通链表，而是红黑树，无论更新还是添加都用红黑树的方法去做
    			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    		else { 
    			// 中间：一点一点遍历，完成更新或者添加操作
    			for (int binCount = 0; ; ++binCount) { 
    				// 中间：p是链表中的第一个节点，p.next是链表中的第二个节点，那e就是链表中的第二个节点，如果该节点为空，那么结果是true
    				if ((e = p.next) == null) { 
    					// 中间：创建一个新的节点，然后赋值给p节点的next，这就是默认在链表尾部添加值
    					p.next = newNode(hash, key, value, null);
    					// 中间：如果链表中的节点数目大于等于8，那么将把该链表变成红黑树
    					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    						// 中间：只有哈希表不是null或者哈希表长度大于等于64，才会将链表变成红黑树
    						treeifyBin(tab, hash);
    					break;
    				}
    				// 中间：如果链表中某个节点的key和该key相等，那就进行更新操作
    				if (e.hash == hash &&
    					((k = e.key) == key || (key != null && key.equals(k))))
    					break;
    				// 将e赋值给p，相当于p是e的prev
    				p = e;
    			}
    		}
    		// 中间：如果e不为空，说明找到了对应的key，否则就是找到最好也没找到key，那么e就是null，而p就是链表中的最后一个节点
    		if (e != null) {  // existing mapping for key
    			// 中间：获取该节点的老值
    			V oldValue = e.value;
    			// 中间：onlyIfAbsent是false，所以结果是true
    			if (!onlyIfAbsent || oldValue == null)
    				// 中间：将新值更新到节点中
    				e.value = value;
    			// move node to last，这是官方注释，代表将该节点移动到链表尾部
    			afterNodeAccess(e);
    			// 中间：返回老值
    			return oldValue;
    		}
    	}
    	++modCount;
    	// 初次/中间：判断哈希表中的实际节点数目，如果该数目大于threshold（默认开始是16的0.75倍，也就是12），那么将进行哈希表扩容
    	if (++size > threshold)
    		resize();
    	// 初次/中间：possibly remove eldest，这是官方注释，代表将移除最老的节点，和LRU算法有关，由于evict是false，所以不会用到，因此不在分析，不相信的话可以看一下内存代码呢！
    	afterNodeInsertion(evict);
    	// 初次/中间：如果是新值，那么将返回null
    	return null;
    }
    
    // 调整哈希表大小
    final Node<K,V>[] resize() { 
    	// 初次：table是null，所以oldTab也是null
    	// 中间：table有值，所以oldTab也有值
    	Node<K,V>[] oldTab = table;
    	// 初次：oldTab是null，所以oldTab == null是true，那么结果是0
    	// 中间：oldTab有值，所以oldTab == null是false，那么结果是哈希表的长度
    	int oldCap = (oldTab == null) ? 0 : oldTab.length;
    	// 初次：threshold是0
    	// 中间：如果使用0.75作为加载因子，那么threshold将是哈希表长度的0.75倍，在其他代码中，我们也会根据哈希表中值的数量与threshold进行比较，最终决定是否扩容
    	int oldThr = threshold;
    	int newCap, newThr = 0;
    	// 初次：oldCap是0，所以结果是false
    	// 中间：oldCap是哈希表的长度，只有这种情况oldCap才大于0，所以结果是true
    	if (oldCap > 0) { 
    		// 中间：比较哈希表长度和MAXIMUM_CAPACITY（即1073741824），一般都是小于该值的，如果大于该值，那么threshold将等于Integer.MAX_VALUE（即2147483647）
    		if (oldCap >= MAXIMUM_CAPACITY) { 
    			threshold = Integer.MAX_VALUE;
    			return oldTab;
    		}
    		// 初次：oldCap是0，所以oldCap << 1也是0，所以小于MAXIMUM_CAPACITY（即1073741824），前半部分结果是true，oldCap是0，但是DEFAULT_INITIAL_CAPACITY是16，所以后半部分结果是false，因此不会执行里面的代码
    		// 中间：由于HashMap的默认初始化容量就是16，所以oldCap肯定大于等于16，但是oldCap << 1也还是挺小的，所以前半部分是true，而后半部分肯定也是true，但是你要注意到newCap已经变成了oldCap的两倍
    		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    				 oldCap >= DEFAULT_INITIAL_CAPACITY)
    			// 中间：oldThr等于threshold，由于newCap是oldCap的两倍，那么newThr也应该是oldThr的两倍，而这个oldThr正好做到
    			newThr = oldThr << 1; // double threshold
    	}
    	// 初次：虽然本次分析无参构造方法，但是有参构造方法会将threshold赋值，所以oldThr也会大于0，因此newCap也会有值
    	else if (oldThr > 0) // initial capacity was placed in threshold
    		newCap = oldThr;
    	// 初次：以下为默认初始化代码
    	else {                // zero initial threshold signifies using defaults
    		// 初次：DEFAULT_INITIAL_CAPACITY是16，那么newCap就是16
    		newCap = DEFAULT_INITIAL_CAPACITY;
    		// 初次：DEFAULT_LOAD_FACTOR是0.75，DEFAULT_INITIAL_CAPACITY是16，结果是12，所以newThr是12
    		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    	}
    	// 初次：本次讨论的是调用无参构造的情况，newThr是12，所以不等于0；如果讨论单参构造的情况，将会执行上面else if (oldThr > 0)中的代码，因此newThr是0，所以会执行下面的代码；
    	// 中间：newThr也不会是0，所以结果是false
    	if (newThr == 0) { 
    		// 初次：现在讨论的是调用单参构造的情况，newCap是2的幂，假设是16，而loadFactor是0.75，因此ft是12
    		float ft = (float)newCap * loadFactor;
    		// 初次：现在讨论的是调用单参构造的情况，newCap很小，ft也很小，而这两个常量都很大，所以结果是true，因此newThr是ft，即newThr是12
    		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    				  (int)ft : Integer.MAX_VALUE);
    	}
    	// 初次：newThr是12，所以threshold是12
    	// 中间：newThr是某值，所以threshold也是该值
    	threshold = newThr;
    	@SuppressWarnings({ "rawtypes","unchecked"})
    		// 初次：newCap是16，所以newTab的大小是16
    		// 中间：newTab的大小是newCap
    		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    	table = newTab;
    	// 初次：oldTab是null，所以结果是false
    	// 中间：oldTab不是null，所以结果是true，以下操作是将老哈希表中原来的值复制到新哈希表中
    	if (oldTab != null) { 
    		// 中间：oldCap是老哈希表长度
    		for (int j = 0; j < oldCap; ++j) { 
    			Node<K,V> e;
    			// 中间：oldTab[j]用来获取老哈希表数组中第一个节点，然后赋值给e
    			if ((e = oldTab[j]) != null) { 
    				// 中间：将oldTab[j]置空，便于GC
    				oldTab[j] = null;
    				// 中间：e.next代表链表中下一个节点，如果为空，代表链表中只有一个节点
    				if (e.next == null)
    					// 中间：如果链表中只有一个节点，所以将该节点的元素值复制到新哈希表的节点中
    					newTab[e.hash & (newCap - 1)] = e;
    				// 中间：该链表有多个节点，那么该情况处理该链表是红黑树的情况
    				else if (e instanceof TreeNode)
    					// 中间：这是红黑树的知识，不在深入
    					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    				else {  // preserve order
    					// 中间：如果链表中有多个节点，但是还没有形成红黑树，那么就使用以下循环代码进行复制操作，不在分析
    					Node<K,V> loHead = null, loTail = null;
    					Node<K,V> hiHead = null, hiTail = null;
    					Node<K,V> next;
    					do { 
    						next = e.next;
    						if ((e.hash & oldCap) == 0) { 
    							if (loTail == null)
    								loHead = e;
    							else
    								loTail.next = e;
    							loTail = e;
    						}
    						else { 
    							if (hiTail == null)
    								hiHead = e;
    							else
    								hiTail.next = e;
    							hiTail = e;
    						}
    					} while ((e = next) != null);
    					if (loTail != null) { 
    						loTail.next = null;
    						newTab[j] = loHead;
    					}
    					if (hiTail != null) { 
    						hiTail.next = null;
    						newTab[j + oldCap] = hiHead;
    					}
    				}
    			}
    		}
    	}
    	return newTab;
    }
    
    // 创建节点
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { 
    	return new Node<>(hash, key, value, next);
    }
    
    // 节点
    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;
    	}
    }
    
    // 将链表变成红黑树
    final void treeifyBin(Node<K,V>[] tab, int hash) { 
    	int n, index; Node<K,V> e;
    	// 中间：只有哈希表不是null或者哈希表长度大于等于64，才会将链表变成红黑树，否则调整哈希表大小
    	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    		resize();
    	else if ((e = tab[index = (n - 1) & hash]) != null) { 
    		// 中间：以下操作将链表转换成红黑树，以下不在分析
    		TreeNode<K,V> hd = null, tl = null;
    		do { 
    			TreeNode<K,V> p = replacementTreeNode(e, null);
    			if (tl == null)
    				hd = p;
    			else { 
    				p.prev = tl;
    				tl.next = p;
    			}
    			tl = p;
    		} while ((e = e.next) != null);
    		if ((tab[index] = hd) != null)
    			hd.treeify(tab);
    	}
    }

#### 2.5、键和值都可以是null ####

1、key == null依然可以得到0，所以键可以是null

static final int hash(Object key) { 
    	int h;
    	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

2、不涉及value的相关方法，所以value可以是null  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 1]

#### 2.6、如果设置HashMap的初始化容量，但是初始化容量不是2的幂次方，那么会将该容量变成2的幂次方 ####

public HashMap(int initialCapacity, float loadFactor) { 
    	if (initialCapacity < 0)
    		throw new IllegalArgumentException("Illegal initial capacity: " +
    										   initialCapacity);
    	if (initialCapacity > MAXIMUM_CAPACITY)
    		initialCapacity = MAXIMUM_CAPACITY;
    	if (loadFactor <= 0 || Float.isNaN(loadFactor))
    		throw new IllegalArgumentException("Illegal load factor: " +
    										   loadFactor);
    	// 为加载因子赋值为0.75
    	this.loadFactor = loadFactor;
    	// 保证threshold变成2的幂次方，然后第一次调用putVal()方法的时候就会将哈希表的容量也变成threshold值
    	this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 保证threshold变成2的幂次方，假设我设置initialCapacity是12,那么出来的结果是16
    static final int tableSizeFor(int cap) { 
    	int n = cap - 1;
    	n |= n >>> 1;
    	n |= n >>> 2;
    	n |= n >>> 4;
    	n |= n >>> 8;
    	n |= n >>> 16;
    	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    final Node<K,V>[] resize() { 
    	int oldThr = threshold;
    	…………
    	// 将threshold赋值给newCap，
    	else if (oldThr > 0) // initial capacity was placed in threshold
    		newCap = oldThr;
    	…………
    	// 初次：如果讨论单参构造的情况，将会执行上面else if (oldThr > 0)中的代码，因此newThr是0，所以会执行下面的代码；
    	if (newThr == 0) { 
    		// 现在讨论的是调用单参构造的情况，newCap是2的幂，假设是16，而loadFactor是0.75，因此ft是12
    		float ft = (float)newCap * loadFactor;
    		// 现在讨论的是调用单参构造的情况，newCap很小，ft也很小，而这两个常量都很大，所以结果是true，因此newThr是ft，即newThr是12
    		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    				  (int)ft : Integer.MAX_VALUE);
    	}
    	// 现在讨论的是调用单参构造的情况，newThr又变成了newCap的0.75倍
    	threshold = newThr;
    }

#### 2.7、get(Object key)方法 ####

// 获取键对应的值
    public V get(Object key) { 
    	Node<K,V> e;
    	// hash()方法在上面已经说过了，这里不再赘述
    	return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    // 根据哈希码和键获取节点
    final Node<K,V> getNode(int hash, Object key) { 
    	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    	// 如果哈希表不为空，并且具有长度，还有根据哈希值可以获取到节点
    	if ((tab = table) != null && (n = tab.length) > 0 &&
    		(first = tab[(n - 1) & hash]) != null) { 
    		// 判断链表中第一个节点是否符合要求
    		if (first.hash == hash && // always check first node
    			((k = first.key) == key || (key != null && key.equals(k))))
    			return first;
    		// 获取链表中的第二个节点
    		if ((e = first.next) != null) { 
    			// 链表中的第一个节点如果是红黑树中的节点，那么使用红黑树去获取对应的节点
    			if (first instanceof TreeNode)
    				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    			// 通过遍历获得链表中和所寻找的key相等的节点
    			do { 
    				if (e.hash == hash &&
    					((k = e.key) == key || (key != null && key.equals(k))))
    					return e;
    			} while ((e = e.next) != null);
    		}
    	}
    	return null;
    }

#### 2.8、remove(Object key)方法 ####

// 删除方法
    public V remove(Object key) { 
    	Node<K,V> e;
    	// hash()方法在前面已经说过了，不在赘述
    	return (e = removeNode(hash(key), key, null, false, true)) == null ?
    		null : e.value;
    }
    
    // 移除相关节点
    final Node<K,V> removeNode(int hash, Object key, Object value,
    						   boolean matchValue, boolean movable) { 
    	Node<K,V>[] tab; Node<K,V> p; int n, index;
    	// 如果哈希表不为空，并且可以通过哈希值从哈希表中获取到到对应的值
    	if ((tab = table) != null && (n = tab.length) > 0 &&
    		(p = tab[index = (n - 1) & hash]) != null) { 
    		Node<K,V> node = null, e; K k; V v;
    		// p是链表中的第一个节点，判断该节点的key是否符合要求
    		if (p.hash == hash &&
    			((k = p.key) == key || (key != null && key.equals(k))))
    			node = p;
    		// 判断链表中的第二个节点是否为空
    		else if ((e = p.next) != null) { 
    			// 如果链表中的第一个节点是红黑树中的，那么将使用红黑树中的方法获取对应的节点
    			if (p instanceof TreeNode)
    				node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
    			else { 
    				// 通过循环遍历找到链表中的该节点
    				do { 
    					if (e.hash == hash &&
    						((k = e.key) == key ||
    						 (key != null && key.equals(k)))) { 
    						node = e;
    						break;
    					}
    					p = e;
    				} while ((e = e.next) != null);
    			}
    		}
    		// 如果确实找到了和key相等的节点，另外matchValue是false，那么!matchValue是true，因此结果是true
    		if (node != null && (!matchValue || (v = node.value) == value ||
    							 (value != null && value.equals(v)))) { 
    			// 如果节点属于红黑树中的节点，那么按照红黑树中的方法删除节点
    			if (node instanceof TreeNode)
    				((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    			// 如果节点就是链表中的第一个节点，那么直接将链表中的第一个节点换成第二个节点就是了
    			else if (node == p)
    				tab[index] = node.next;
    			// 如果节点不是链表中的第一个节点，那么p就是e的上一个节点，该操作就是将需要删除的上一个节点的下面指向被删除节点的下一个节点
    			else
    				p.next = node.next;
    			++modCount;
    			--size;
    			// 虽然上面已经写了p.next = node.next，但是被删除的节点依然指着其他节点，该方法就是要删除该节点和下面节点的联系，方便GC清除，避免内存泄露
    			afterNodeRemoval(node);
    			return node;
    		}
    	}
    	return null;
    }

## 二、HashTable ##

### 1、结论 ###

HashTable是Map接口的实现类，底层数据结构是哈希表，是线程安全的，默认初始化容量是11，默认加载因子是0.75，默认在链表头部添加节点，按照原来的两倍大小+1进行扩容，键和值都不能是null，无论怎么变化，也不会将链表变成红黑树

### 2、证明 ###

注意：以下代码来自于HashTable类的源码；

#### 2.1、HashTable是Map接口的实现类 ####

public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable

#### 2.2、底层数据结构是哈希表 ####

private transient Entry<?,?>[] table;

#### 2.3、是线程安全的 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 2]

#### 2.4、默认初始化容量是11，默认加载因子是0.75，默认在链表头部添加节点，按照原来的两倍大小+1进行扩容，键和值都不能是null ####

// 代表数字2147483639
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 默认无参构造
    public Hashtable() { 
    	// 默认初始化容量是11，默认加载因子是0.75
    	this(11, 0.75f);
    }
    
    // 双参构造
    public Hashtable(int initialCapacity, float loadFactor) { 
    	if (initialCapacity < 0)
    		throw new IllegalArgumentException("Illegal Capacity: "+
    										   initialCapacity);
    	if (loadFactor <= 0 || Float.isNaN(loadFactor))
    		throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    	if (initialCapacity==0)
    		initialCapacity = 1;
    	// 如果使用无参构造方法，默认加载因子是0.75
    	this.loadFactor = loadFactor;
    	// 如果使用无参构造方法，默认初始化容量是11
    	table = new Entry<?,?>[initialCapacity];
    	// initialCapacity * loadFactor肯定比较小啊，因为后面的MAX_ARRAY_SIZE + 1成2147483640，一般使用都不会大于它的
    	threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

如果想要找到`“默认在链表头部添加节点，按照原来的两倍大小+1进行扩容”`这两个问题的答案，那就需要看put()方法了，跟我一起来看吧！

// 代表数字2147483639
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 添加或者更新
    public synchronized V put(K key, V value) { 
    	// Make sure the value is not null，这是官方注释，所以value不能是null
    	if (value == null) { 
    		throw new NullPointerException();
    	}
    
    	// Makes sure the key is not already in the hashtable，这是官方注释
    	Entry<?,?> tab[] = table;
    	// 由于key要调用hashCode()方法，所以key不能是null
    	int hash = key.hashCode();
    	// 根据hash值获取对应的数组索引
    	int index = (hash & 0x7FFFFFFF) % tab.length;
    	@SuppressWarnings("unchecked")
    	// 获取数组中该索引对应的节点，进而找到这条链表
    	Entry<K,V> entry = (Entry<K,V>)tab[index];
    	// 遍历该链表，如果该链表中的某节点的键和我们方法参数中的键相等，那我们就执行更新操作，当更新完成后，返回老节点
    	for(; entry != null ; entry = entry.next) { 
    		if ((entry.hash == hash) && entry.key.equals(key)) { 
    			V old = entry.value;
    			entry.value = value;
    			return old;
    		}
    	}
    
    	// 程序走到这个地方，说明没有哈希表中所有节点的key都和方法参数中的key不相等
    	addEntry(hash, key, value, index);
    	return null;
    }
    
    // 添加方法
    private void addEntry(int hash, K key, V value, int index) { 
    	modCount++;
    
    	// 将哈希表赋值给tab
    	Entry<?,?> tab[] = table;
    	// 如果哈希表中实际节点数量大于等于threshold(默认是哈希表数组数量的0.75倍)，那就对哈希表进行扩容
    	if (count >= threshold) { 
    		// Rehash the table if the threshold is exceeded
    		rehash();
    
    		tab = table;
    		// 我认为这个更改没有必要，毕竟key没有改变，那么hash值就不会变
    		hash = key.hashCode();
    		// 哈希表改变，那么index也会改变
    		index = (hash & 0x7FFFFFFF) % tab.length;
    	}
    
    	// Creates the new entry.
    	@SuppressWarnings("unchecked")
    	// 获取索引处的节点，也就是链表中的第一个节点，不过也可能是null
    	Entry<K,V> e = (Entry<K,V>) tab[index];
    	// 创建新的节点，让tab表中的第一个节点变成了新节点，然后把链表中原来的第一个节点或者null放在新节点的后面，所以我说默认在在链表头部添加节点
    	tab[index] = new Entry<>(hash, key, value, e);
    	count++;
    }
    
    // Entry节点
    private static class Entry<K,V> implements Map.Entry<K,V> { 
    	final int hash;
    	final K key;
    	V value;
    	// 看来是单向链表
    	Entry<K,V> next;
    
    	// 将链表中的第一个节点变成新的节点，next就是链表中原来的第一个节点，也可能是空的
    	protected Entry(int hash, K key, V value, Entry<K,V> next) { 
    		this.hash = hash;
    		this.key =  key;
    		this.value = value;
    		this.next = next;
    	}
    }
    
    // 对哈希表进行扩容
    protected void rehash() { 
    	// 哈希表长度
    	int oldCapacity = table.length;
    	// 将老哈希表赋值给oldMap
    	Entry<?,?>[] oldMap = table;
    
    	// 将容量扩展为老容量的2倍 + 1
    	int newCapacity = (oldCapacity << 1) + 1;
    	// MAX_ARRAY_SIZE是一个很大的数字，所以一般使用中都是小于0的，不符合要求
    	if (newCapacity - MAX_ARRAY_SIZE > 0) { 
    		if (oldCapacity == MAX_ARRAY_SIZE)
    			// Keep running with MAX_ARRAY_SIZE buckets
    			return;
    		newCapacity = MAX_ARRAY_SIZE;
    	}
    	// 按照新容量给创建链表
    	Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
    	modCount++;
    	// newCapacity是新容量，而loadFactor是加载因子，我们在构造方法中已经赋值了，默认使用0.75，然后MAX_ARRAY_SIZE是一个很大的数字
    	threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    	// 将新链表赋值给哈希表
    	table = newMap;
    
    	// 遍历哈希表（）
    	for (int i = oldCapacity ; i-- > 0 ;) { 
    		// 遍历哈希表中的每一个链表，遍历一次处理一个节点
    		for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { 
    			Entry<K,V> e = old;
    			// 该代码执行之后，e变成old的上一个节点，这次处理的是e，下次处理old
    			old = old.next;
    			// 由于hash值就是通过键的hashCode()来获得的，所以这里可以直接使用e.hash，相当于e.hashCode()，该代码用于计算出新的哈希表数组索引
    			int index = (e.hash & 0x7FFFFFFF) % newCapacity;
    			// 让e的下面指向newMap中链表的第一个节点
    			e.next = (Entry<K,V>)newMap[index];
    			// 让e变成newMap中对应索引处的第一个节点
    			newMap[index] = e;
    		}
    	}
    }

#### 2.5、键和值都不能是null ####

// 添加或者更新
    public synchronized V put(K key, V value) { 
    	// Make sure the value is not null，这是官方注释，所以value不能是null
    	if (value == null) { 
    		throw new NullPointerException();
    	}
    	……
    	// 由于key要调用hashCode()方法，所以key不能是null
    	int hash = key.hashCode();
    	……
    }

#### 2.6、get(Object key) ####

// 获取方法，很简单，不在赘述
    public synchronized V get(Object key) { 
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 
            if ((e.hash == hash) && e.key.equals(key)) { 
                return (V)e.value;
            }
        }
        return null;
    }

#### 2.7、remove(Object key) ####

public synchronized V remove(Object key) { 
    	Entry<?,?> tab[] = table;
    	int hash = key.hashCode();
    	int index = (hash & 0x7FFFFFFF) % tab.length;
    	@SuppressWarnings("unchecked")
    	// e代表链表中的第一个节点
    	Entry<K,V> e = (Entry<K,V>)tab[index];
    	for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 
    		if ((e.hash == hash) && e.key.equals(key)) { 
    			modCount++;
    			// 如果prev不是头结点，此时e是prev的下一个节点，需要删除的不是头结点，那么prev的next等于e节点的下一个节点（注意：删除的是e节点）
    			if (prev != null) { 
    				prev.next = e.next;
    			} else { 
    				// 如果需要删除的就是头结点，直接将链表中的第一个节点变成e的下一个节点（注意：删除的是e节点）
    				tab[index] = e.next;
    			}
    			count--;
    			V oldValue = e.value;
    			// 单单清除一个e节点的值我认为是不行的，毕竟e的下一个节点还有值，只要这个联系存在，GC就无法回收e节点，如果太多了，那就会造成内存泄露
    			e.value = null;
    			return oldValue;
    		}
    	}
    	return null;
    }

## 三、TreeMap ##

### 1、结论 ###

TreeMap是Map接口的间接实现类，底层数据结构是红黑树，不是线程安全的，根据key进行排序

### 2、证明 ###

注意：以下代码来自于TreeMap类的源码；

#### 2.1、TreeMap是Map接口的间接实现类 ####

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
        
    public interface NavigableMap<K,V> extends SortedMap<K,V>
    
    public interface SortedMap<K,V> extends Map<K,V>

#### 2.2、底层数据结构是红黑树 ####

// root是红黑树的根
    private transient Entry<K,V> root;
    
    // Entry是红黑树的节点
    static final class Entry<K,V> implements Map.Entry<K,V> { 
    	K key;
    	V value;
    	Entry<K,V> left;
    	Entry<K,V> right;
    	Entry<K,V> parent;
    	boolean color = BLACK;
    
    	/** * Make a new cell with given key, value, and parent, and with * {@code null} child links, and BLACK color. */
    	Entry(K key, V value, Entry<K,V> parent) { 
    		this.key = key;
    		this.value = value;
    		this.parent = parent;
    	}
    	……
    }

#### 2.3、不是线程安全的 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 3]

#### 2.4、根据key进行排序 ####

// 无参构造方法
    public TreeMap() { 
    	// 键比较器，默认为空，将会使用compareTo()方法进行比较，另外可以使用单参构造方法来自己创建比较器
        comparator = null;
    }
        
    // 分析一下put方法
    public V put(K key, V value) { 
    	// 初次：root是null，那么t是null，root是红黑树的根
    	// 中间：root有值，那么t是有值，root是红黑树的根
    	Entry<K,V> t = root;
    	// 初次：t是null
    	if (t == null) { 
    		// 如果key是null，那早点爆出异常
    		compare(key, key); // type (and possibly null) check
    		// 创建根节点
    		root = new Entry<>(key, value, null);
    		size = 1;
    		modCount++;
    		return null;
    	}
    	int cmp;
    	Entry<K,V> parent;
    	// split comparator and comparable paths
    	// 初次/中间：获得比较器
    	Comparator<? super K> cpr = comparator;
    	// 注意：以下分析中自己创建了属于自己的比较器
    	if (cpr != null) { 
    		do { 
    			parent = t;
    			cmp = cpr.compare(key, t.key);
    			if (cmp < 0)
    				t = t.left;
    			else if (cmp > 0)
    				t = t.right;
    			else
    				return t.setValue(value);
    		} while (t != null);
    	}
    	// 注意：以下分析中没有创建属于自己的比较器
    	else { 
    		if (key == null)
    			throw new NullPointerException();
    		@SuppressWarnings("unchecked")
    			// 转变之后才可以调用比较器
    			Comparable<? super K> k = (Comparable<? super K>) key;
    		// 调用比较器，如果更新值，更新之后直接返回；也有可能添加到某位置，这就需要先做好添加的铺垫，先找到需要添加的合适位置；这属于红黑树中的语法
    		do { 
    			parent = t;
    			// 调用比较器比较值，用来确定是更新还是找到添加新节点的位置
    			cmp = k.compareTo(t.key);
    			if (cmp < 0)
    				t = t.left;
    			else if (cmp > 0)
    				t = t.right;
    			else
    				// 如果某节点的键和插入的键相等，那么将新值设置到该节点中，相当于更新操作
    				return t.setValue(value);
    		} while (t != null);
    	}
    	// 创建新节点
    	Entry<K,V> e = new Entry<>(key, value, parent);
    	// 将新节点添加到合适的位置
    	if (cmp < 0)
    		parent.left = e;
    	else
    		parent.right = e;
    	// From CLR，估计也是一种算法吧，不在分析了
    	fixAfterInsertion(e);
    	size++;
    	modCount++;
    	return null;
    }

## 四、类图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70]: /images/20221023/5514a2e39f5b4c70ae2cfcda36fffb0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 1]: /images/20221023/29ef2c4711f243e8b0dbc85a31f8f12f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 2]: /images/20221023/d1fe44ecea314c3e8a7fe8b21cc1fb91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 3]: /images/20221023/222752989ed345deaabe9d2cf3c34e21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDQ5OTYz_size_16_color_FFFFFF_t_70 4]: /images/20221023/827c18cb4b2e4929865d4834ddaf37a9.png