hashCode

義往昔 2月前 ⋅ 63 阅读

尽管理解hashCode()和equals()方法所扮演的角色非常重要,但我们无需每次都从头实现,大多数ide都提供了生成自定义的hashCode()和equals()实现。从java 7 之后,Objects.hash() 工具方法可以方便实现:

IntelliJ IDEA 生成下面实现:

@Override
public int hashCode() {
    int result = (int) (id ^ (id >>> 32));
    result = 31 * result + name.hashCode();
    result = 31 * result + email.hashCode();
    return result;
}

 public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) id;
        hash = 31 * hash + (name == null ? 0 : name.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        logger.info("hashCode() called - Computed hash: " + hash);
        return hash;
    }

 

除了上述基于IDE的hashCode实现,也可以通过其他工具进行有效实现,如Lombok

在User类仅需要增加@EqualsAndHashCode注解就可以实现@EqualsAndHashCode

类似使用 Apache Commons Lang’s HashCodeBuilder 类也可以生成 hashCode() 实现

public class User {
    public int hashCode() {
        return new HashCodeBuilder(17, 37).
        append(id).
        append(name).
        append(email).
        toHashCode();
    }
}

这里我们注意到所有这些实现都以某种形式使用数字31——这是因为31有一个很好的属性——它的乘法运算可以被比标准乘法运算快的位移所代替:

31 * i == (i << 5) - i

详细: https://segmentfault.com/a/1190000010799123

处理哈希冲突

哈希表的内在行为支持这些数据结构的相关实现:即使哈希算法非常有效,两个或多个对象不相等,也有可能产生相同的哈希值。所以它们的哈希值指向相同的桶,虽然它们有不同的key值。

通常这种场景我们称为哈希冲突,存在多种方式可以处理,每个都尤其优劣。java HashMap采用单独链接方法处理冲突:

当两个或多个对象指向相同的桶,这些对象在桶中以linked List方式存储。这种情况下,哈希表是linked List的数组,每个相同哈希值对象被追加至桶的linked List中。

最坏情况下,几个桶仅绑定一个linked List,则在list中检索对象只能是线性搜索。哈希冲突说明为什么实现有效hashCode方法非常重要。

java 8 提供了HashMap的增强实现,如果桶大小超出一定阈值,会使用tree map代替 linked List,只有时间复杂度从O(logn)提升至O(n)。

全文原文 : 

https://blog.csdn.net/neweastsun/article/details/80530993

 


注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: