java - HashSet 的底层数据结构

Question

ArrayList底层dataStructure是Array，LinkedList是Link对象，HashMap或HashTable可以是LinkedList或Tree的Array，HashSet中使用的数据结构是什么

Answer 1

根据Javadoc，HashSet 的支持数据结构是 HashMap。

JDK 1.6 代码验证了这一点：

public HashSet() {
    map = new HashMap<>();
}

Answer 2

散列的幼稚想法是将元素存储到数组中的位置索引处，计算如下：

• 通过处理元素的数据并生成一个整数值来获取元素的element_hash_code（“散列”元素的想法大致意味着“将其磨碎”）
• 使用简单的 mod 操作映射到数组的范围

所以这些可以通过数组或链表来完成。

在java中HashSet使用HashMap内部

从源代码

public HashSet() {
    map = new HashMap<E,Object>();
}

Answer 3

HashSet 在内部使用 HashMap 来存储数据。而且我相信 HashMap 是一个 Entry 对象数组。

了解HashMap内部结构的相关帖子：

https://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally

Answer 4

HashMap 和 HashSet（基于 HashMap）的底层数据结构是哈希表http://en.wikipedia.org/wiki/Hash_table。在 HashMap 源代码中，它看起来像一个条目数组

Entry<K,V>[] table;

... 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
...