Java中的hash结构总结：HashSet、HashMap、HashTable
Java中的hash结构总结：HashSet、HashMap、HashTable
Java中常用的Hash结构只有HashSet和HashMap两类，HashTable是HashMap的一种子类，下面对它们的继承关系，接口方法进行总结。
Java集合框架概述
因为三者都是Java集合体系中的一部分，所以先介绍java的集合框架
HashSet是Collection接口中Set中的一部分，所以这里展示Collection的接口继承树
HashMap和HashTable是Map接口中的一部分，这是Map的接口继承树
一、HashSet部分
1.HashSet接口方法（也就是Collection的接口方法）
因为 Set接口是Collection的子接口，set接口没有提供额外的方法
添加
add(Object obj)
addAll(Collection coll)
获取有效元素的个数
int size()
清空集合
void clear()
是否是空集合
boolean isEmpty()
是否包含某个元素
boolean contains(Object obj)：是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c：也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。
删除
boolean remove(Object obj)：通过元素的equals方法判断是否是要删除的那个元素，只会删除找到的第一个元素 boolean removeAll(Object coll)：去当前集合的差集
取两个集合的交集
boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响c
集合是否相等
boolean equals(Object obj)
转成对象数组
Object[] toArray()
获取集合对象的哈希值
hashCode()
遍历
iterator()：返回迭代器对象，用于集合遍历
2.HashSet特点
HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类
HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
HashSet具有以下特点：
（1）不能保证元素的排列顺序；
（2）HashSet不是线程安全的
（3）集合元素可以是null
HashSet 集合判断两个元素相等的标准： 两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。
3.向HashSet中添加元素的过程（不影响调用，了解了会更清楚原理）
当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）
如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功
4.HashSet的子类——LinkedHashSet
区别：它同时使用双向链表维护元素的次序，这使得元素看起来是以插入
顺序保存的。这主要体现在迭代的遍历过程中，普通的HashSet遍历时元素的顺序和插入顺序没有关系，而LinkedHashSet可以保证遍历到的顺序和插入顺序相同。
4.1 程序验证HashSet与LinkedHashSet的无序与有序
验证代码 1：
package com.atwb.test;
import java.util.*;
public class TestHash {
public static void main(String[] args) {
Set<Integer> normalHash = new
HashSet<>();
Set<Integer> linkedHash = new
LinkedHashSet<>();
for (int i = 0; i < 20; i++) {
normalHash.add(i);
linkedHash.add(i);
}
System.out.println(normalHash);
System.out.println(linkedHash);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
结果：
这么看，两者似乎没有区别 但是换个输入看看
package com.atwb.test;
import java.util.*;
public class TestHash {
public static void main(String[] args) {
Set<Integer> normalHash = new
HashSet<>();
Set<Integer> linkedHash = new
LinkedHashSet<>();
normalHash.add(30);
normalHash.add(10);
normalHash.add(50);
normalHash.add(20);
linkedHash.add(30);
linkedHash.add(10);
linkedHash.add(50);
linkedHash.add(20);
System.out.println(normalHash);
System.out.println(linkedHash);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
结果：
这么看HashSet确实是无序的，而LinkedHashSet是有序的
那么第一次测试为什么两者的结果为什么是一样的呢？
仔细回想，不难发现hashset底层使用hashmap来实现的，set的元素存放在map的key上面。
对于hashmap来讲，它的主体是一个Entry数组，Entry又是一个链表，因此hashmap的存储过程如下：
1.计算key的hash值
2.把得到的hash值作为数据下标去存储到Entry数组。在这里可能出现不一样的key的得到的hash值相等，如果相等，就把新的value存到当前下标下保存的Entry里面（Entry是链表）
由此可见，hashset实际上存储元素的时候进行了获取hash的操作，而对于第一次测试用例中的遍历0-19来说，他们的hash值就是自身，所以根据这个hash值得到数组的下标存储元素后，表现出来就是有序的。
也就是恰好输入顺序的哈希值就是有序的。
二、HashMap部分
1.HashMap接口方法
添加 、 删除、修改操作 ：
Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据
元素 查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等
元 视图操作的方法：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合
2.HashMap特点
HashMap是 Map 接口 使用频率最高的实现类。
允许使用null键和null值，与HashSet一样，不保证映射的顺序。
HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等
HashMap 判断两个 value 相等的标准是：两个 value 通过 equals() 方法返回 true
一个key-value构成一个entry，所有的entry构成的集合是Set:无序的、不可重复的
3.向HashMap添加元素的过程
向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry[]数组中要存储的位置i。如果位置i上没有元素，则entry1直接添加成功。如果位置i上已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次比较entry1中key和其他的entry。如果彼此hash值不同，则直接添加成功。如果hash值不同，继续比较二者是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素
4.HashMap的子类——LinkedHashMap
类似于LinkedHashSet与HashSet的关系，LinkedHashMap 是 HashMap 的子类，在HashMap存储结构的基础上，使用了一对双向链表来记录添加，元素的顺序，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致
三、HashTable部分
因为这个现在不怎么常用，并且大部分原理和方法都和HashMap相同，这里只做简单介绍
Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap，
Hashtable是线程安全的。
Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value
与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序
Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。
四、区别总结：HashSet、HashMap与HashTable
HashSet与HashMap
类型 实现接口 是否有序 是否允许类型重复 是否允许存在null
HashSet collection 否 否 是
HashMap Map 否 否 使用key-value来映射和存储数据，key必须唯一，value可以重复
HashTable Map 否 否 否
PS：表中是否有序是指实际存储位置，而不是遍历顺序，即使是LinkedHashMap这种也是无序的，它只是添加了双向链表用来记录添加顺序用来遍历而已
————————————————
版权声明：本文为CSDN博主「SOS团团员A」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34332616/article/details/114692538