HashMap、HashTable和HashSet

常见的数据结构有数组结构链表结构哈希表结构

  1. 数组结构:存储区间连续,内存占用严重、空间复杂度大
    优点:随机读取和修改效率高,原因是数组内存空间连续,所以随机访问性强、查找速度快
    缺点:插入和删除的效率低,因插入数据,这个位置后面的数据在内存中后需要往后移动;删除数据,这个位置后面的数据在内存中都需要向前移动,且大小固定不宜动态拓展。
  2. 链表结构:存储区间离散、占用内存宽松、空间复杂度小
    优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活
    缺点:不能随机查找,每次查找都需要从第一个数据开始遍历,查找效率低
  3. 哈希表结构:结合了数据结构和链表结构的一种数据结构,从而实现了查找效率高效的同时,修改数据也很高效。

HashMap:

HashMap简介:HashMap是基于哈希表实现的,每个元素都是一个key-value对,其内部通过单链表解决冲突,内存不足(超越了阈值)时,可以自动增长

HashMap特点

  1. HashMap时非线性安全的,只适用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap
  2. HashMap实现了Serializable接口,支持序列化,实现了Cloneable接口,能被克隆。继承自AbstractMap类。
  3. HashMap内部维护了一个存储数据的Entry数组,数组默认是16位,采用链表解决冲突,每一个Entry本质上是个单向链表。
  4. HashMap中的key和value允许为null,key为nul的键值对永远放在以table[0]为头节点的链表中。
  5. 删增是在链表上完成的,而查询只需扫描部分
  6. 查找 HashMap集合的key,会先后调用两个方法,HashCode和Equal方法,这两个方法都需要重写。

HashMap中put()和get()的实现原理

  1. map.put(key , value)实现原理:
    a. 首先将key、value封装到Node对象中;
    b. 底层调用hashCode()方法得出哈希值,然后通过哈希算法转化为数组的下标;
    c. 如果下标位置上没有任何元素,就将Node添加到这个位置上。如果下标位置上有链表,则将key与该链表中的所有节点的key进行equal,如果equal都返回false,就将新节点议案加到链表的末尾,如果有一个节点equal返回了true,就用value覆盖掉这个节点上的value
  2. map.get(key)的实现原理
    a. 先调用HashCode(key)方法获得哈希值,并用哈希算法转化为数组的下标
    b. 如果数组下标位置上什么也没有,则返回null;如果有链表,则拿着key与链表中的节点中的key进行equal,如果equal都返回false,则返回null,如果有一个节点的equal返回true,则返回这个节点的value值。

扩容机制

提到扩容机制需要先明白几个变量:

size:记录HashMap的底层数组中已用的槽的数量;
threshold:HashMap的阈值,用于判断是否需要调整HashMap的容量,计算方式为threshold = 容量 * 加载因子
加载因子:表示哈希表在其容量自动增加之前可以达到多满的一种尺度,如果加载很大,对空间的利用更充分,但是查找效率会降低;如果加载因子太小。那么表中的很多空间还没有使用就开始扩容了,对空间造成浪费。默认值为0.75
容量:表示哈希表中槽的数量,即哈希表的长度,初始容量是创建哈希表的容量,如果不指明初始容量,则默认为16
特别注意:无论我们指定容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方

扩容时间:当size大于threshold的时候进行扩容。

扩容过程:
扩容是新建了一个HsahMap的底层数组,然后调用transfer方法,将HashMap的全部元素添加到新的HashMap中,同时重新计算元素在新的数组中的索引位置。很明显,扩容是非常耗时的操作。
HashMap共有四个构造方法,构造方法中提到了两个很重要的参数:初始容量和加载因子,这两个参数是影响HashMap性能的重要参数。

HashMap红黑树:

什么是HashMap红黑树?
将HashMap表中的单一链表长度过长时,此时修改或者查找HashMap中的数据就会非常耗时,时间效率为O(n),即将所有数据遍历一边,效率降低;为了能够恢复HashMap快速查找和修改数据的优点,将单一链表用红黑树进行替换,此时的时间效率会缩减到O(logn),效率不会因为链表长度过长而导致效率降低。
什么时候采用HashMap红黑树,什么时候采用HashMap?
当HashMap表中的单一链表长度大于8时,链表结构就会转化为红黑树结构;当单一链表长度小于6的时候,又会由红黑树结构转化为链表结构。

HashTable

HashTable的数据结构跟HashMap相同,此处主要讲解HashTable与HashMap之间的区别。

  1. 继承的父类不同:
    HashMap继承自AbstractMap类,
    HashTable继承自Dictionary类,Dictionary类是是一个已经被废弃的类,父类都已经被废弃了,子类HashTable自然就很少有人使用;
    但是两者都实现了Map接口,支持序列化和克隆。
  2. HashMap线程不安全,只能在单线程中使用;
    HashTable对数据的读写等操作提供了锁保护,所以线程是安全的,支持多线程中使用;
    HashMap的迭代器是fail-fast迭代器,故当有其他线程改变HashMap结构时,将会抛出异常;而HashTable不是fail-fast迭代器。
  3. 包含的contains方法不同:
    HashMap没有contains方法,但包括containsValue和containsKey方法;
    HashTable保留了contains方法,与containsValue效果一样,同时也提供了containsKey和containsValue方法。
  4. 是否允许null值:
    HashMap允许key和value为null值,当key为null值时,但为空的键值对必须放置在table[0]为头节点的链表中。
    HashTable键值对都不能为空。否则报出指针异常的错误。
  5. 计算Hash值和数组下标索引方法不同:
    HashMap计算Hash值的方法为先调用HashCode方法计算出来一个Hash值,再将Hash与右移16位后相异或,从而得到新的Hash值;
    HashTable通过计算key的HashCode()得到的Hash值就是最终Hash值。
    HashMap求Hash值对应的位置索引时,index = (n - 1) & hash,将哈希表的大小
    固定为2的幂,因为是取模得到索引值,故这样子取模时,不需要做除法;
    HashTable取位置索引:int index = (hash & 0x7FFFFFFF) % table.length, &0x7FFFFFFF是为了将负的Hash值转化为正值,因为Hash值可能为负数。
  6. 扩容方式不同:
    HashMap哈希扩容必须要求为原容量的2倍,而且一定是2的幂次倍扩容结果;
    HashTable扩容为原容量的2倍加一。
  7. 解决Hash冲突方法不同:
    采用链地址法解决Hash冲突:将所有关键字为同义词的记录存储在同一个线性表中。即Hash出来的哈希地址不存储key值,而出存储一个key的链表,当发生冲突时,将同义的key加入链表。
    HashMap会在冲突数量大于8时,将链式结构换为红黑树结构,当冲突数量小于6的时候,再将红黑树结构换位链式结构;
    HashTable一直使用链式结构。
  8. 内存初始值大小不同:
    HashMap初始大小为16,HashTable初始大小为11.

HashSet

底层原理:HashSet底层完全就是在HashMap的基础上包了一层,只不过存储的时候value默认存储了一个object类型的静态常量,取的时候也是只返回key,看起来像是List一样。HashSet的四个构造方法都是初始化一个HashMap,初始容量、装填因子Add()、Remove()、contains()方法都是直接调用HashMap的实现。

需要重写HashCode() 和 Equals() ,需要这两个方法确保存储的值没有相等。Equals默认比较的是两个对象的内存地址。

HashMap与HashSet的区别:

  1. HashMap实现了Map接口,HashSet实现了Set接口;
  2. HashMap存储键值对,HashSet仅存储对象;
  3. HashMap调用put()向map中添加元素,HashSet调用add()向set中添加元素;
  4. HashMap使用key计算HashCode,HashSet使用成员对象计算HashCode值,对于两个对象来说HashCode值可能相同,所以需要equals方法判断对象的相等性。
  5. HashMap相对于HashSet较快,因为它是使用唯一的键获取对象。
上一篇:面试系列-HashMap和Hashtable的区别


下一篇:查找算法:哈希表