关于HashSet和HashMap的区别以及底层实现原理_hashmap和hashset的区别和分析

前言:

HashSet和HashMap是面试中比较常问的一个问题，他的难点主要在于它的底层原理和处理冲突的方式。他们两个是Java中常见的两种集合类型，它们的主要区别在于如何存储和访问元素。接下来我们展开具体讲一讲。

一、HashSet：

1、什么是HashSet？
HashSet是一种无序集合它实现了Set接口，它不允许集合中有重复的值，当添加元素时，HashSet首先使用哈希函数计算元素的索引，然后将元素添加到该索引对应的链表中。当需要查找元素时，HashSet会使用哈希函数计算元素的索引，并在相应的链表中搜索它。
2、HashSet常见的构造函数：

(1) HashSet（）
该构造函数用于构建一个空的HashSet对象，其中默认初始容量为16，默认加载因子为0.75。如果我们希望创建一个名为 hs 的空 HashSet，则可以将其创建为：

HashSet<E> hs = new HashSet<E>();
//其实也可以写成,以下类推
Set<E> hs = new HashSet<E>();
1
2
3

(2) HashSet(int initialCapacity)
initialCapacity就是初始容量,在对象创建时指定initialCapacity。

HashSet<E> hs = new HashSet<E>(int initialCapacity);
1

(3)HashSet(int initialCapacity, float loadFactor)
该构造函数用于构建一个空的HashSet对象，其中在创建对象时指定了initialCapacity和loadFactor。

HashSet<E> hs = new HashSet<E>(int initialCapacity, float loadFactor);
1

3、HashSet常用的方法：

（1）添加元素add()

因为HashSet是纯Key模型，所以相同的值不会存进去。

public static void main(String[] args) {
        Set<String> set=new HashSet<String>();
        set.add("world");
        set.add("hello");
        set.add("good");
        //加入重复元素；
        set.add("world");
        System.out.println("set中的值为:"+set);
    }
1
2
3
4
5
6
7
8
9

输出的结果：

从结果中可以看出，虽然有两个world但是只存了一次。

（2）删除元素remove()

public static void main(String[] args) {
        Set<String> set=new HashSet<String>();
        set.add("world");
        set.add("hello");
        set.add("good");
        //加入重复元素；
        set.add("world");
        System.out.println("set中的值为:"+set);
        set.remove("hello");
        System.out.println("删除后set中的元素为："+set);
1
2
3
4
5
6
7
8
9
10

（3）判断是否包含元素contains()， 判断是否为空isEmpty()，获得大小size()；

public static void main(String[] args) {
        Set<String> set=new HashSet<String>();
        set.add("world");
        set.add("hello");
        set.add("good");
        //加入重复元素；
        set.add("world");
        System.out.println("set中的值为:"+set);
        boolean ret=set.contains("China");
        System.out.println("是否包含元素："+ret);
        boolean isFull=set.isEmpty();
        System.out.println("是否为空："+isfull);
        int len=set.size();
        System.out.println("set中值得元素个数："+len);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(4)遍历HashSet:
使用iterator()遍历，也就是迭代器。
还有一种方法是for循环。

public static void main(String[] args) {
        Set<String> set=new HashSet<String>();
        set.add("world");
        set.add("hello");
        set.add("good");
        set.add("中国");
        //加入重复元素；
        set.add("world");
        //使用Iterator迭代器遍历；
        Iterator<String> integer=set.iterator();
        System.out.println("使用迭代器遍历:");
        while (integer.hasNext()){
            System.out.print(integer.next()+",");
        }
        System.out.println();
        System.out.println("使用for循环遍历");
        for (String s:set) {
            System.out.print(s+",");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这里是引用HashSet 操作的时间复杂度：HashSet的底层数据结构是 hashtable。因此，HashSet
的添加、删除和查找（包含方法）时间复杂度需要O(1)时间。

二、HashMap

1.什么是HashMap？

• HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
• HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
• HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。
• HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。
• 如果添加相同的key，则会覆盖原来的k-v，等同于修改。

2、HashMap的实现原理：

HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
如图：

当链表长度到达8时，升级成红黑树结构。

让我们看看底层实现的代码。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;计算得到哈希值
    final K key;
    V value;
    Node<K,V> next;
}

interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
1
2
3
4
5
6
7
8
9
10
11

• 根据哈希值判断该数应该放到链表的那个位置；

• 这是表的默认容量；

• 这是表的最大容量；
  
  - 这是负载因子的值；

• 链表转为红黑树的临界值

3、HashMap的扩容机制

• JDK1.7的扩容条件：

1、当前存储的数量大于等于阈值；
2、发生hash碰撞；
特点： 先扩容，再添加（扩容使用的头插法）。
缺点： 头插法会使链表发生反转，多线程环境下可能会死循环。

- JDK.18的扩容条件：

• 1、当前存储的数量大于等于阈值。
• 2、当某个链表长度>=8，但是数组存储的结点数size() < 64时。

特点： 先插后判断是否需要扩容（扩容时是尾插法）。
缺点： 多线程下，1.8会有数据覆盖。

源码实现：

void resize(int newCapacity) {
　　　　Entry[] oldTable = table;
　　　　int oldCapacity = oldTable.length;
　　　　//判断是否有超出扩容的最大值，如果达到最大值则不进行扩容操作
　　　　if (oldCapacity == MAXIMUM_CAPACITY) {
　　　　　　threshold = Integer.MAX_VALUE;
　　　　　　return;
　　　　}
 
　　　　Entry[] newTable = new Entry[newCapacity];
　　　　// transfer()方法把原数组中的值放到新数组中
　　　　transfer(newTable, initHashSeedAsNeeded(newCapacity));
　　　　//设置hashmap扩容后为新的数组引用
　　　　table = newTable;
　　　　//设置hashmap扩容新的阈值
　　　　threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
　　}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4、哈希冲突

（1）什么是哈希冲突：
当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，即称为发生了哈希冲突。简单来说就是哈希函数算出来的地址被别的元素占用了。
（2）解决哈希冲突的方法：

• 链地址法（Separate Chaining）:将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
• 开放地址法（Open Addressing）:当发生哈希冲突时，通过一定的探测方法（如线性探测、二次探测、双重哈希等）在哈希表中寻找下一个可用的位置。这种方法的优点是不需要额外的存储空间，适用于元素数量较多的情况。
• 再哈希法（Rehashing）:同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。虽然不易发生聚集，但是增加了计算时间。
  5、HashMap和Hashtable的区别（面试题）：
• HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null。Hashtable是线程安全的，多个线程可以共享一个Hashtable。
• 因为 Hashtable 使用了 synchronized 给整个方法添加了锁，所以相比于 HashMap 来说，它的性能不如 HashMap。
• HashMap可以使用null作为key，不过建议还是尽量避免这样使用。HashMap以null作为key时，总是存储在table数组的第一个节点上。而Hashtable则不允许null作为key。