九, 散列与散列码
HashMap 使用 equals() 判断当前的键是否与表中存在的键相同.
正确的 equals() 方法需满足一下条件:
1) 自反性. x.equals(x) 是 true;
2) 对称性. x.equalse(y) 返回 true y.equals(x) 也得是 true;
3) 传递性. x.equals(y) 返回 true ,y.equals(z) 返回 true , x.equals(z) 返回 true;
4) 一致性. 如果对象中用于等价比较的信息没有变, 那么无论多少次 x.equals(y) 返回值不会变
5)x.equals(null) 返回 false ; 注意:(null).equals(x) 报空指针.
强调: 默认的 Object.equals() 只比较对象的地址, 因此如果使用自己的类作为 HashMap 的 Key, 必须同时重载 hashCode() 和 equals().
hashCode() 并不需要总是能够返回唯一的标识码, 但是 equals() 方法必须严格的判断两个对象是否相等, 作为键必须唯一否则系统报错.
- @Override
- public boolean equals(Object o) {
- return o instanceof T && (i.equals(((T) o).i)));
- }
instanceof 检查了此对象是否为 null , 是 null 则返回 false.
为速度而散列
以线性查询的是最慢的查询方式, 存储一组元素最快的数据结构是数组, 所以使用它来标识键的信息 (注意, 这里说的是键信息不是键本身).
由于数组不能调整容量, 所以数组不保存键本身, 而是通过键对象生成一个散列码, 将其作为数组的下标, 这个散列码就是由 Object 中的, 或自己的类覆盖的 hashCode() 生成的.
数组固定的问题解决了, 但是键可以产生相同的下标, 也就是说可能会有冲突. 数组多大不重要, 任何键总能在数组中找到它的位置.
于是, 查询一个值的过程首先就是计算散列码, 然后使用散列码查找数组. 如果能够保证没有冲突 (如果被查询的值的数量是固定的, 就有可能).
通常, 冲突由外部链接处理; 数组并不直接保存值, 而是保存值的 list. 然后对 list 中的值使用 equals() 方法进行线性查询.
这部分查找会比较慢, 但是如果散列函数好的话, 数组每个位置就有较少的值.
因此, 不是查询整个 List 而是快速的跳转到数组的某个位置, 只对很少的元素进行比较. 这就是 HashMap 会如此快的原因.
我们把散列表的数组称为 bucket(桶), 为了散布均匀且速度快, 桶的容积通常使用质数或者 2 的整数次方, 用 LinkedList 填充桶.
put() 操作, 计算 key 的 hashCode(), 找到桶中的位置, 看 LinkedList 内容, 有值用 equals() 与值的 key 相比, 相等就替换, 不等或者没有值就在尾部加上新值.
覆盖 hashCode()
桶下标值是无法控制的, 这个值依赖于具体的 HashMap 对象的容量, 而容量的改变与容器的充满程度和负载因子有关. hashCode() 生成的结果, 经过畜栏里后成为桶位的下标.
Joshua Blochw 指出为写出一份像样的 hashCode 给出了知道:
1) 给 int 变量 result 赋予某个非 0 常量,
2) 为对象内每个有意义的域 f(既每个可以做 equals() 操作的域) 计算一个 int 散列码 c:
域类型: 计算:
- boolean c=(f?0:1)
- byte,char,short,int c=(int)f
- float c=(int)(f^(f>>>32))
- double long I =Double.doubleToLongBits(f); c=(int)(I^(I>>>32))
Object, 其 equals() 调用这个域的 equals() c=f.hashCode()
数组 对每个元素应用上述规则
3) 合并计算得到散列码
result = 37*result+c
来源: https://www.cnblogs.com/xcgShare/p/11718155.html