HashMap

31
五月
2021

Hashmap是有数组+链表+红黑树组成的数据结构。HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体。 只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树。数组是用来确定桶的位置,利用元素的key的hash值对数组长度取模得到. 链表是用来解决hash冲突问题,当出现hash值一样的情形,就在数组上的对应位置形成一条链表。在hashmap插入数据的时候通过计算key的hash值,如果hash值没有碰撞就直接放到数组对应的链表中。如果hash值碰撞了,就以链表形式存放。如果碰撞导致链表过长,就会把链表转换成红黑树。从hashmap获取数据,根据key计算出hash值,如果链表中第一个节点就命中直接返回。如果有冲突,通过key.equals去查找对应的元素。Hashmap默认长度16,在插入数据的时候,通过load factor因子判断是否需要扩容,默认0.75。

Hashmap与hashtable的区别:

两者最主要的区别在于Hashtable是线程安全,而HashMap则非线程安全。
Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,我们平时使用时若无特殊需求建议使用HashMap,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合(Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例,简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理)。

HashMap可以使用null作为key,而Hashtable则不允许null作为key。
虽说HashMap支持null值作为key,不过建议还是尽量避免这样使用,因为一旦不小心使用了,若因此引发一些问题,排查起来很是费事。
HashMap以null作为key时,总是存储在table数组的第一个节点上。

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

HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75。
HashMap扩容时是当前容量翻倍即:capacity*2,Hashtable扩容时是容量翻倍+1。即:capacity*2+1

两者计算hash的方法不同,Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模。

哈希冲突

然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员