HashSet（HashMap）工作原理

HashSet（HashMap）工作原理

Administrator 493 2023-08-05

HashSet是Java中的一种集合类，它使用哈希表（Hash Table）来存储元素。在哈希表中，元素的存储位置是根据它们的哈希码（Hash Code）来确定的

  • hashCode()方法

    • 每个Java对象都有一个hashCode()方法，它返回一个32位的整数值，表示对象的哈希码。哈希码是根据对象的内容计算出来的，通常情况下，如果两个对象相等（通过equals()方法比较），那么它们的hashCode()方法应该返回相同的值，但反之则不一定成立（这种情况称为哈希冲突）。

  • 哈希表

    • HashSet内部使用了一个哈希表来存储元素。哈希表实际上是一个数组，数组的每个位置被称为“桶”（Bucket）。当你往HashSet中添加元素时，HashSet会首先计算该元素的hashCode()方法的返回值。

  • 计算索引

    • 计算出的hashCode值经过一定的处理（通常是取绝对值，然后对数组长度取余），得到一个在哈希表中的索引，这个索引就表示了元素在数组中的存放位置。这个索引对应的桶就是元素的存储位置。

  • 解决哈希冲突

    • 由于不同的对象可能会有相同的哈希码，所以在计算得到的索引位置可能已经有其他元素存在。这种情况称为哈希冲突。为了解决冲突，HashSet使用了一些方法，最常见的是在同一个索引位置使用链表或者更高效的红黑树来存储多个元素，从而确保同一个索引位置可以存储多个元素。

  • 查找元素

    • 当你需要查找一个元素时，HashSet会首先根据要查找元素的hashCode计算出索引，然后在对应的桶中查找元素。如果在链表或者红黑树中找到了对应的元素，就说明元素存在于集合中。

HashSet利用对象的hashCode()方法来计算哈希码，然后通过哈希码计算出在哈希表中的索引位置，最终将元素存储在对应的桶中。这种设计使得在集合中查找、插入和删除元素的操作可以在平均情况下达到常数时间复杂度，从而实现高效的元素存储和查找

当涉及到底层实现细节时，查看源代码是理解的一个很好的方法。下面我将用一些简化的Java源代码来说明HashSet是如何通过哈希码确定对象的位置的

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    // ...

    // 哈希表，用于存储元素
    private transient HashMap<E,Object> map;

    // 虚拟的常量，用于作为哈希表中的value，因为HashSet的实现依赖于HashMap
    private static final Object PRESENT = new Object();

    // 构造方法
    public HashSet() {
        map = new HashMap<>();
    }

    // 添加元素
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    // ...

    // 内部实现类，用于存储元素的哈希表
    private static class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
        // ...

        // 哈希桶数组，用于存储元素
        transient Node<K,V>[] table;

        // ...

        // 计算哈希码
        final int hash(Object key) {
            int h = key.hashCode();
            return (key == null) ? 0 : h ^ (h >>> 16);
        }

        // 计算元素在哈希表中的索引
        static int indexFor(int h, int length) {
            return h & (length-1);
        }

        // 添加元素到哈希表
        public V put(K key, V value) {
            int hash = hash(key);
            int i = indexFor(hash, table.length);

            for (Node<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    return oldValue;
                }
            }

            addEntry(hash, key, value, i);
            return null;
        }

        // ...

        // 哈希表中的一个节点
        static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;

            // ...
        }
    }
}

上述代码只是一个简化版的示例，实际的HashSet和HashMap实现要更加复杂。关键点是：

  • HashSet内部实际上使用了一个HashMap来存储元素，HashMap中使用了哈希桶数组来存储节点。

  • 当调用add()方法将元素添加到HashSet时，实际上是通过HashMap的put()方法将元素添加到哈希表中。

  • 在put()方法中，首先会计算元素的哈希码，然后使用哈希码计算出在哈希桶数组中的索引位置。

  • 如果该索引位置已经存在其他节点（可能是哈希冲突），则会遍历链表或红黑树（根据节点数量）查找合适的位置来插入元素。

总之，HashSet利用了HashMap的哈希表实现，通过计算哈希码并选择合适的索引位置来确定对象在集合中的位置。这种机制保证了高效的元素查找和存储。要深入理解更多细节，最好还是查看Java源代码的实现。

源码中的 hash() 方法可能是一个疑点，他的作用及原理如下:
假设我们有一个哈希码 h，二进制表示为：11001010101110011011100110100101

现在，我们进行无符号右移操作 h >>> 16，将低 16 位移到高位，得到：00000000000000001100101010111001

接下来，我们进行异或操作 h ^ (h >>> 16)，对应的位进行异或操作：

11001010101110011011100110100101
00000000000000001100101010111001
--------------------------------
11001010101110010111001100011100

通过异或操作，我们将原始哈希码的高位和低位进行了混合。现在，如果我们将得到的结果再转化为十进制，得到：3361659324。

这个结果相比于原始哈希码 2864585453，已经发生了很大变化。这种混合的效果在位级别上实际上是将原始哈希码的不同部分交织在一起，增加了分布的随机性。这样的随机性有助于减少哈希冲突的发生，从而提高了哈希表的性能。

总之，位运算 h ^ (h >>> 16) 的作用是将原始哈希码的高位和低位进行混合，生成一个在位级别上更随机的结果，从而提高哈希码的分布性。

面试题

为什么重写equals（）方法，就一定要重写hashCode（）方法？

在Java中，当重写了 equals() 方法，目标是要在逻辑上判断两个对象是否相等，即它们的内容是否相同。然而，在涉及散列集合（如 HashSet、HashMap 等）时，不仅需要考虑逻辑上的相等，还需要确保哈希码相等的对象被放置在哈希表中同一个位置。这样才能正确地执行插入、查找、删除等操作。

如果只重写了 equals() 方法，但没有重写 hashCode() 方法，就有可能出现以下问题：

  • 不一致的哈希码： 两个对象在 equals() 方法中被判断为相等，但由于它们的 hashCode() 方法返回不同的哈希码，它们在散列集合中被当作不同的键插入。这会导致你无法正确查找或删除这些对象。

  • 无法正确覆盖： 在散列集合中，如果你希望用新的对象覆盖旧的对象（基于 equals() 判断相等），你需要确保新对象的哈希码与旧对象的哈希码相同。否则，你的新对象将被错误地放置在哈希表的另一个位置。

所以，为了保证逻辑相等的对象在散列集合中能够被正确地处理，必须同时重写 equals() 和 hashCode() 方法。这样，可以确保相等的对象拥有相同的哈希码，从而保证它们被正确处理并存储在散列集合中。

总之，重写 hashCode() 方法主要是为了保证逻辑相等的对象在散列集合中能够正确处理。如果仅在一般的逻辑判断中使用 equals() 方法，那么重写 hashCode() 并不是必需的。

hash java