去重算法，觉得解法不对

Question

算法：
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
解法：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

疑问？这个解法我感觉有问题。会不会可能出现不同的值存在同一个hashcode值，
出现的话，那这个解法就有问题？？

Answer 1

    /**
     * Returns a hash code for an {@code int} value; compatible with
     * {@code Integer.hashCode()}.
     *
     * @param value the value to hash
     * @since 1.8
     *
     * @return a hash code value for an {@code int} value.
     */
    public static int hashCode(int value) {
        return value;
    }

Integer hashcode 的值就是他本身的 value。

Answer 2

就算有相同的hashcode又怎么了? 你这算法又不是通过比较哈希值来判断相同的.
不影响.

Answer 3

首先，你这个不是去重算法，从问题描述中，并没有去重，而只是查重。

其次，对于具体的哈希算法来说，是可能存在不同的值出现相同哈希值可能的（哈希值碰撞了），但对你现在的整数来说，在特定语言下，整数本身也有有效值范围的时候，可能不一定有碰撞。

Answer 4

看样子是 Java 代码。

HashSet 使用 Objects.equals()) 来判断是否相同，而 Objects.equals() 的代码中是这样写的：

public static boolean equals(Object a, Object b) {
    return (a == b) || (a != null && a.equals(b));
}

也就是说，是用 Object.equals 重载来判断是否相同的，对于 Integer 类型来说，是直接使用的 intValue() 来比较：

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

回过头来，继续说 HashSet。HashSet 是通过 HashMap 来实现，而判断元素是否存在是通过其 containsKey 方法来判断的，而 containsKey() 又直接使用了 getNode()。

在 getNode() 的代码中确实计算了 Hash，也就是直接/间接使用了 hashCode() 的结果，但这个 Hash 值只用做初步判断（用于快速失败判断），如果相等，继续使用 equals() 进行精确的判断，如果不等，那没啥好说的，肯定匹配不上了啊。当然这个快速 Hash 对比只是用于比较复杂的数据结构提高性能，对于 Integer 来说，其 Hash 就是 intValue，反而会多进行一次 equals 判断，降低性能。不过整数比较很快，可以忽略这点性能损失。

Answer 5

哈希值的确是会碰撞的，这个本身就是 hashMap 这类的需要处理的问题。

比如我使用了一个长度为 100 的数组作为 hash表 原始长度，然后对你输入的参数进行哈希操作，这里我们简单的直接取余数（真实哈希取值更复杂）；

输入 20 ， 取余 20 % 100 ，被放在下标为 20 的 hash 表中，但是输入为 120 的时候，其余数还是 20 这个时候，就需要处理碰撞问题, java 中使用 红黑树 来处理，也就是 hashMap 中的每个元素都是 红黑树 , 而相同 hash 的内容被放在同一个下标的 红黑树 中，由于 红黑树 的特性就是 平衡树 结构，其搜索复杂度为 O(logN) 对数复杂度，因此我们近似的将 hash 表的复杂度看成为 O(1) 复杂度；