Hash Table、HashMap、HashSet学习

前言

本文用于介绍关于Hash Table、HashMap、HashSet的学习。
本文中有的地方说的是哈希，有的地方说的是散列，只需记住，在本文中哈希就是散列，散列就是哈希。

Hash Table（散列表）

散列表也就是哈希表，在散列表中使用到了红黑树和链表（下面会介绍），无论是HashMap还是HashSet，它们都是基于散列表实现的，所以先简单介绍一下散列表。

基本概念

散列表是根据键key直接访问值value的数据结构，它是由数组演化而来，利用了数组支持按下标进行随机访问数据的特性。

在数组中，索引下标就可以作为key，数组中的元素就可以作为value，我们可以通过下标索引（key）直接获取到数组中的元素（value）。

散列函数

散列表的key可以是各种各样的数据结构，而数组下标是整数，所以将各种各样数据结构的key映射为数组下标的函数就叫散列函数（哈希函数）。可以表示为hashValue=hash(key)。

散列函数的基本要求：

• 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标
• 如果key1==key2，那么经过散列函数计算出的hashValue一定相等，即hash(key1)==hash(key2)
• 如果key1!=key2，那么经过散列函数计算出的hashValue一定不相等，即hash(key1)!=hash(key2)（几乎不可能）

散列冲突（哈希碰撞）

实际上想找到一个散列函数能做到不同的key计算出的hashValue值都不同是几乎不可能的，这就是散列冲突，也就是指多个key的hashValue相等，映射到了同一个数组下标。

拉链法

拉链法是解决哈希冲突的方法。在散列表中，数组的每个下标位置我们可以称为桶或者槽，每个桶（槽）会对应一条链表，所有散列值（hashValue）相同的元素我们会放到相同槽位对应的链表中，如下。

红黑树

拉链法的使用的链表我们可以改造为效率更高的红黑树，这里简单介绍一下红黑树。

红黑树：是一种自平衡的二叉搜索树（二叉搜索树：对于树中的任意一个节点，左子树节点的值都小于该节点的值，右子树节点的值都大于该节点的值），红黑树与二叉搜索树不同的就是有一个平衡机制，可以避免二叉搜索树的最差情况（链表）。

红黑树的特性：

• 节点要么是红色，要么是黑色
• 根节点是黑色
• 叶子节点都是黑色的空节点
• 红黑树中的红色节点的子节点是黑色的
• 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有性质，完成性质的目标就是为了保证平衡。

红黑树的时间复杂度

• 查找：红黑树也是二叉搜索树，所以查找的时间复杂度为O(logn)
• 添加：从根节点开始找到元素添加的位置，时间复杂度为O(logn)，添加完成后涉及到时间复杂度为O(1)的旋转操作，所以整体时间复杂度为O(logn)
• 删除：从根节点开始找到元素删除的位置，时间复杂度为O(logn)，删除完成后涉及到时间复杂度为O(1)的旋转操作，所以整体时间复杂度为O(logn)

时间复杂度分析

• 插入元素：只需通过散列函数计算出相应的槽位，插入槽位对应的链表的末尾即可，时间复杂度为O(1)
• 查找和删除元素：也是先通过哈希函数计算出相应的槽位，再遍历槽位对应的链表进行插入和删除
  • 在平均情况下（元素分布比较平均）基于链表法解决哈希散列冲突的时间复杂度是O(1)
  • 散列表可能退化为链表（所有元素通过散列函数计算出的槽位都是同一个槽位），查询时间复杂度就变为了O(n)
  • 可以将链表法中的链表改为其他更高效的数据结构，如红黑树（如下图），时间复杂度为O(logn)

将链表法中的链表改为红黑树还有一个好处：可以防止DDos攻击（分布式拒绝服务攻击，指处于不同位置的多个攻击者对一个或多个目标进行攻击，或者一个攻击者控制位于不同位置的多个机器对目标同时实施攻击），DDos攻击可以伪装大量的key插入链表中，这样我们如果是使用的链表的话访问时效率就会非常低。

HashMap

基础

HashMap是Java中一个非常重要的数据结构，用于存储键值对（key-value）信息。它基于哈希表实现，提供了时间复杂度为O(1)的查找、插入和删除操作，所以从算法层面来说，我们常使用HashMap来判断一个元素是否在集合中。

HashMap具有以下特性：

• 键值对存储：存储的是键值对，每个键（key）都有一个值（value）
• 键的唯一性：在HashMap中，键是唯一的，如果先后插入两个键相同的值时，后插入的值会将前面一个值覆盖
• 无序：不保证元素的顺序，元素的顺序可能会随着插入和删除操作而变化
• 线程不安全：HashMap是线程不安全的，在多线程环境下，如果多个线程同时访问和修改HashMap，可能造成数据不一致的情况。

方法使用

要使用HashMap，我们需要先对其进行定义：

//键为整数类型，值为字符串类型
HashMap<Integer,String> hashMap=new HashMap<Integer,String>();

基本的增删改查

• 增加数据

//添加键的同时添加值
hashMap.put(1,"aaa");
hashMap.put(2,"bbb");
hashMap.put(3,"ccc");

• 删除数据

//根据键删除值
hashMap.remove(1);//清空所有数据
hashMap.clear();

• 修改数据

//根据键修改数据
hashMap.replace(2,"bbbb");

• 查询数据

//根据键查询数据
hashMap.get(2);

除此之外还存在一个getOrDefault()方法：

hashMap.getOrDefault(2,defaultValue);

这个方法用于查询是否存在这个key对应的value，如果没有，返回defaultValue。

String defaultValue=hashMap.getOrDefault(4,"ddd");
System.out.println(defaultValue);//由于并未添加键为4，值为ddd的数据，所以输出ddd

其他的方法

• HashMap是否为空

hashMap.isEmpty();

• 获取HashMap中键值对的数量

int size=hashMap.size();

• 是否存在某个键值对

hashMap.containsKey(1);//是否存在键为1的键值对
hashMap.containsValue("aaa");//是否存在值为"aaa"的键值对

• 分别返回所有键和值

Set<Integer> list1=hashMap.keySet();//所有键的集合
Collection<String> list2=hashMap.values();//所有值的集合

实现原理

HashMap的数据结构：底层使用散列表（哈希表）数据结构，即数组+链表或数组+红黑树

• 当我们使用put方法向HashMap中添加元素时，会利用key的hashCode计算出hashValue（哈希值），对应两种结果

  • hashValue相同，key也相同：覆盖原始值
  • hashValue相同，key不相同：将当前的key-value存入链表或红黑树中

• 使用get方法获取数据时，先找到hashValue对应的下标（桶或槽），再进一步通过key找到value

需要注意的是：

• 在jdk1.8之前：拉链法只有将数组和链表结合，遇到哈希冲突就将冲突的值添加到链表中
• 在jdk1.8之后：当链表长度大于阈值（默认为8）并且数组长度达到64时，就会将链表转为红黑树，这样做可以减少搜索时间还能防止DDos

HashSet

HashSet是一个不允许有重复元素的集合，但允许存在null值。

特性：

• 不允许重复：不允许存储重复的元素，使用add方法存储重复的元素时会返回false
• 无序：内部元素的存储是无序的，就算添加元素时是有序的，HashSet也不保证遍历时的顺序与添加时的一致
• 高效：添加、删除、查找的时间复杂度都为O(1)

基础操作

• 定义一个HashSet

Set<Integer> set=new HashSet<Integer>();

• 添加值

set.add(100);

• 删除元素

set.remove(100);
//移除所有元素
set.clear();

• 判断元素是否存在

set.contains(100);

去重原理

HashSet通过hashCode()（用于计算出hashValue）和equals()（比较对象的地址值是否相同）方法实现去重。

在向HashSet添加元素时：会先调用hashCode()方法来计算出hashValue来判断对象加入的位置，如果该位置没有值，则直接插入；如果发现该位置存在值，则会调用equals()方法来判断两个对象是否相同（对象不同就是哈希冲突，上面有介绍），如果相同则添加失败返回false。

学习分享到此结束，希望能对你有所帮助！