深入集合类系列——HashMap和HashTable的区别

时间:2022-03-09 16:58:39

含义:HashMap是基于哈希表的Map接口的非同步实现。允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

数据结构:HashMap实际上是一个链表散列的数据结构,即数组和链表的结合体。

深入集合类系列——HashMap和HashTable的区别

 

HashMap存数据的基本流程:

    1、当调用put(key,value)时,首先获取key的hashcode,int hash = key.hashCode(); 

    2、再把hash通过一下运算得到一个int h. 

hash ^= (hash >>> 20) ^ (hash >>> 12);

int h = hash ^ (hash >>> 7) ^ (hash >>> 4);

为什么要经过这样的运算呢?这就是HashMap的高明之处。先看个例子,一个十进制数32768(二进制1000 0000 0000 0000),经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗?或许这样还看不出什么,再举个数字61440(二进制1111 0000 0000 0000),运算结果是65263(二进制1111 1110 1110 1111),现在应该很明显了,它的目的是让“1”变的均匀一点,散列的本意就是要尽量均匀分布。那这样有什么意义呢?看第3步。

    3、得到h之后,把h与HashMap的承载量(HashMap的默认承载量length是16,可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。)进行逻辑与运算,即 h & (length-1),这样得到的结果就是一个比length小的正数,我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index,这是HashTable的改进,HashTable中的算法只是把key的 hashcode与length相除取余,即hash % length,这样有可能会造成index分布不均匀。还有一点需要说明,HashMap的键可以为null,它的值是放在数组的第一个位置。

    4、我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素(这个元素是HashMap内部定义的一个类Entity, 基本结构它包含三个类,key,value和指向下一个Entity的next),没有的话就创建一个Entity对象,在 table[index]位置上插入,这样插入结束;如果有的话,通过链表的遍历方式去逐个遍历,看看有没有已经存在的key,有的话用新的value替 换老的value;如果没有,则在table[index]插入该Entity,把原来在table[index]位置上的Entity赋值给新的 Entity的next,这样插入结束。

流程总结:key->hashcode->h->index->遍历链表->插入

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

(2)

hash ^= (hash >>> 20) ^ (hash >>> 12);

int h = hash ^ (hash >>> 7) ^ (hash >>> 4);

(3)h&(length-1)得到index

(4)遍历链表并插入

 

1、HashTable的实现原理(源代码)

 

含义:Hashtable 也是一个散列表,它存储的内容是键值对(key-value)映射。

 

Hashtable 继承于Dictionary,实现了MapCloneableJava.io.Serializable接口。

 

Hashtable 的函数都是同步的,这意味着它是线程安全的。

 

它的keyvalue都不可以为null

 

此外,Hashtable中的映射不是有序的。

 

Hashtable 的实例有两个参数影响其性能:初始容量 加载因子。容量:是哈希表中桶的数量,初始容量,就是哈希表创建时的容量。注意,哈希表的状态为 open:在发生“哈希冲突”的情况下,单个桶会存储多个条目,这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

 

通常,默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查找某个条目的时间(在大多数 Hashtable 操作中,包括 get put 操作,都反映了这一点)。

 

 

HashMapHashTable的区别

 

1)两者最主要的区别在于Hashtable是线程安全,而HashMap则非线程安全

 

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,我们平时使用时若无特殊需求建议使用HashMap,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

 

 

 

(2)HashMap可以使用null作为key,而Hashtable则不允许null作为keyHashMapnull作为key时,总是存储在table数组的第一个节点上。

 

 

 

(3)HashMap是对Map接口的实现,HashTable实现了Map接口和Dictionary抽象类

 

 

 

4HashMap的初始容量为16Hashtable初始容量为11,两者的填充因子默认都是0.75

 

HashMap扩容时是当前容量翻倍即:capacity*2Hashtable扩容时是容量翻倍+1:capacity*2+1

 

 

 

5)两者计算hash的方法不同

 

Hashtable计算hash是直接使用keyhashcodetable数组的长度直接进行取模

 

int hash = key.hashCode();

 

int index = (hash & 0x7FFFFFFF) % tab.length;

 

HashMap计算hashkeyhashcode进行了二次hash,以获得更好的散列值,然后对table数组长度取摸,key->hashcode->h->index->遍历链表->插入

 

 

6HashMapHashtable的底层实现都是数组+链表结构实现