JDK源码学习笔记——HashMap
hashmap与hashtable数据结构几乎是相同的(数组+链表),核心方法的实现也大致相同
主要讨论不同,比较两者不同从jdk源码入手
一、父类不同
hashmap父类abstractmap
hashtable父类dictionary
dictionary类源码已注释被弃用
hashtable类源码注释也表明hashtable已被淘汰
* java collections framework</a>. unlike the new collection * implementations, {@code hashtable} is synchronized. if a * thread-safe implementation is not needed, it is recommended to use * {@link hashmap} in place of {@code hashtable}. if a thread-safe * highly-concurrent implementation is desired, then it is recommended * to use {@link java.util.concurrent.concurrenthashmap} in place of * {@code hashtable}.
// 如果你不需要线程安全,那么使用hashmap,如果需要线程安全,那么使用concurrenthashmap。hashtable已经被淘汰了,不要在新的代码中再使用它。
二、synchronize
hashtable是线程安全的,它的每个方法中都加入了synchronize方法。
hashmap不是线程安全的,在多线程并发的环境下,使用hashmap时就必须要自己增加同步处理。
(虽然hashmap不是线程安全的,但是它的效率会比hashtable要好很多。这样设计是合理的。在我们的日常使用当中,大部分时间是单线程操作的。hashmap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的concurrenthashmap。concurrenthashmap虽然也是线程安全的,但是它的效率比hashtable要高好多倍。因为concurrenthashmap使用了分段锁,并不对整个数据进行锁定。)
三、初始容量和扩充容量
hashmap初始容量16,扩容默认为原来容量的2倍
hashtable初始容量11,扩容默认为原来容量的2倍+1
四、hash值算法不同
hashmap: 具体原因可参考jdk源码学习笔记——hashmap
1.int hash = (h = key.hashcode()) ^ (h >>> 16) ;
2.int index = (table.length - 1) & hash;
3.tablesizefor()方法保证数组容量一定是2的次幂
hashtable:
1.int hash = key.hashcode();
2.int index = (hash & 0x7fffffff) % tab.length;
五、put时的不同
1、hashmap支持key==null value==null,hash方法专门有对key==null的处理
static final int hash(object key) { int h; return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16); }
hashtable不支持null
public synchronized v put(k key, v value) { // make sure the value is not null if (value == null) {// value==null抛异常 throw new nullpointerexception(); } // makes sure the key is not already in the hashtable. entry<?,?> tab[] = table; int hash = key.hashcode();// key==null抛异常 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; } } addentry(hash, key, value, index); return null; }
2、jdk1.8 hashmap引入了红黑树,链表超过最大长度(8),将链表改为红黑树再添加元素
3、hash碰撞之后的处理
hashmap:在链表尾加入元素
hashtable:在链表头加入元素
参考资料: