Hashtable、HashMap、TreeMap
Hashtable、HashMap、TreeMap都是比较常见的一些Map实现,它们都是 key-value
键值对的形式存储和操作数据的容器类,同时他们的元素中不能有重复的key,一个key也只能映射一个value值。
下面我从不同的维度来分别说说这三个集合,文章中涉及到的源码版本是 JDK8
底层数据结构
-
Hashtable
和HashMap
底层都是采用数组存储数据 -
TreeMap
底层是采用红黑树存储数据
元素特性
Hashtable
Hashtable
中存储的 key
和 value
都不能为 null
,这个从它的源码实现是可以看出来的
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. Entry tab[] = table; int hash = key.hashCode(); ...//省略部分 return null; }
这是 Hashtable
添加元素的源码实现,从开头的if判断就可以发现它的 value
值是不允许为 null
的,而它的 key
虽然没有显式判断,但是在执行 int hash = key.hashCode();
这句代码时,如果 key
为 null
的话,代码执行到这里程序就崩了,所以从侧面也反应出 key
也不能为 null
HashMap
HashMap
中存储的 key
和 value
都允许为 null
,这个依然是从源码中看出来的。
//HashMap的put方法具体实现比较复杂代码比较多,这里我只贴出添加元素时涉及到key和value的相关代码 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Node newNode(int hash, K key, V value, Node next) { return new Node(hash, key, value, next); } TreeNode newTreeNode(int hash, K key, V value, Node next) { return new TreeNode(hash, key, value, next); } static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ... } //TreeNode最终还是继承自Node,所以这里就不贴出TreeNode的构造函数了
从上面的几段代码中可以看到在将 key-value
添加到 HashMap
中时没有任何地方会使用它们,因此 key
和 value
都是可以为 null
的
但是一个 HashMap
中只能有一个 key
为 null
,但是可以有多个 value
为 null
TreeMap
TreeMap
中如果用户未实现 Comparator
接口,则 key
不能为 null
,如果实现了 Comparator
接口,那么 key
能否为 null
则需要根据 Comparator
接口的具体实现有关。 value
则是可以为 null
。至于原因,我们依然通过源码来寻求答案
public V put(K key, V value) { ... Comparator cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); Comparable k = (Comparable) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp 0) t = t.right; else return t.setValue(value); } while (t != null); } ... return null; }
通过上面的代码可以很明显的看到当成员变量 comparator
为空时( Comparator
接口未实现),有明显的 key
的非空判断,而当实现了该接口后,这会通过 Comparator
接口的 compare
方法比较当前 key
与 TreeMap
中已存在的 key
是否相等,所以这个时候 key
能否为 nul
就跟 Comparator
接口的 compare
方法具体实现有关了。
注意这段代码
cmp = k.compareTo(t.key); if (cmp 0) t = t.right; else return t.setValue(value);
从上面的代码中我们还可以看出 TreeMap
的 key
是有序的,而且当前节点的 key
比其左子树节点的 key
要大,而比右子树节点的 key
要小。
有序性
-
Hashtable
和HashMap
都是无序的 -
TreeMap
的key
是有序的,有序的原因在前面分析其put
源码的时候已经说过了。要注意的是这里是key
是有序的,而不是其value
是有序的,而且其默认是升序排序方式(深度优先搜索),对于其排序方式,可以自定义实现Comparator
接口来自定义排序规则
初始化和扩容方式
Hashtable
- 默认初始化容量为11个
- 容量阈值默认为当前容量的0.75倍,当集合数据大于等于阈值时就会进行扩容
- 不要求底层数组的容量一定为2的幂次方
- 扩容时会将容量变为原来的2倍加1
- 在初始化时就会创建底层数组
- 扩容时会创建一个扩容后的新数组,然后将原来数组的数据拷贝到新数组中
private void addEntry(int hash, K key, V value, int index) { ... if (count >= threshold) {//数据个数大于等于阈值时进行扩容 rehash(); ... } ... } //扩容函数 protected void rehash() { int oldCapacity = table.length; Entry[] oldMap = table; //此处将oldCapacity左移一位,即将其扩大一倍 int newCapacity = (oldCapacity < 0) { if (oldCapacity == MAX_ARRAY_SIZE) return; newCapacity = MAX_ARRAY_SIZE; } Entry[] newMap = new Entry[newCapacity]; modCount++; //重新计算容量阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; //拷贝数据 for (int i = oldCapacity ; i-- > 0 ;) { for (Entry old = (Entry)oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry)newMap[index]; newMap[index] = e; } } }
HashMap
- 默认初始化容量为16个
- 容量阈值默认为当前容量的0.75倍,当集合数据大于等于阈值时就会进行扩容
- 底层数据的容量要求一定是2的幂次方
- 扩容时会将容量变为原来的2倍
- 初始化时不会创建底层数组,而是在调用put方法添加数据时再创建底层数据
- 扩容时会创建一个扩容后的新数组,然后将原来数组的数据拷贝到新数组中
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//初始化创建底层数组 ... if (++size > threshold)//元素个数大于等于阈值则进行扩容 resize(); afterNodeInsertion(evict); return null; } //初始化或扩容函数 final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) {//MAXIMUM_CAPACITY=2^30 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) = DEFAULT_INITIAL_CAPACITY)//此处的newCap = oldCap << 1则是进行数组扩容一倍 newThr = oldThr < 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//重新计算新的阈值 } threshold = newThr; .... return newTab; }
TreeMap
TreeMap
线程安全性
Hashtable
其方法都采用了 synchronized
修饰,因此是线程安全的,不会出现两个线程同时对数据进行操作的情况,它保证了线程安全性。但也因为这样导致其在多线程环境下使用此集合效率低下,因为一个线程访问其同步方法时,其他访问 Hashtable
的线程都会处于阻塞状态,现在已不推荐使用此集合。
HashMap
HashMap
的方法没有采用 synchronized
修饰,所以是非线程安全的,在程序中任一时刻可能会存在多个线程同时修改其数据,从而导致数据不一致。
在多线程环境下,我们可以使用下面两种方式使用 HashMap
- 使用
Collections.synchronizedMap()
方法将HashMap
转换为线程安全的SynchronizedMap
包装类,其内部也是使用synchronized
来达到同步效果,只不过此时锁住的是一个Object
类型的成员变量,和锁住HashMap
对象本身效果是一样,效率也比较低下,仅仅适合用在并发度不高的情景。 - 使用
ConcurrentHashMap
集合,相较于Hashtable
锁住的是对象整体,ConcurrentHashMap
基于lock
实现锁分段技术。首先将Map
存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap
不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升
TreeMap
HashMap
的方法没有采用 synchronized
修饰,所以 TreeMap
也是非线程安全的。
在多线程环境下建议使用 ConcurrentSkipListMap
代替
HashMap的哈希冲突
HashMap
采用 链地址法 来解决哈希冲突,对哈希冲突或链地址法不了解的同学请参考我的另外一篇文章 Hash冲突解决方法
但是在 HashMap
中对链地址法采用了一点点变化,对于哈希冲突导致出现同义词元素显示采用单链表存放,当这个链表大小超过一个阈值(TREEIFY_THRESHOLD=8)且 HashMap
的大小大于等于另一个容量阈值(MIN_TREEIFY_CAPACITY = 64),就会把这个单链表该造为树形结构。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { 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; } ... } } ... } ... return null; } final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { //HashMap的元素大小大于等于MIN_TREEIFY_CAPACITY则将该单链表改造成红黑树 //树改造逻辑 } }
为什么要改造呢,我的理解是这样的:
key
原创文章,严禁随意转载。欢迎大家添加个人微信讨论交流,添加时请备注:博客。