Java中hashMap为什么无符号移动16位，为什么要异或运算） / 开普饭

由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的）
1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；

2、如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；

3、如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；

4、两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。
在hashMap中，如何进行查找，存储数据？
hashMap存储的结构是数组+链表的存储结构

table数组用于存储key-value键值对transient Node<K,V>[] table;

数组的类型是Node<K,V>,每个数组的索引下存放一个链表

static class Node<K,V> implements Map.Entry<K,V> {        final int hash;        final K key;        V value;        //指向下一个节点的指针        Node<K,V> next;        Node(int hash, K key, V value, Node<K,V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }        public final K getKey()        { return key; }        public final V getValue()      { return value; }        public final String toString() { return key + "=" + value; }        public final int hashCode() {            return Objects.hashCode(key) ^ Objects.hashCode(value);        }        public final V setValue(V newValue) {            V oldValue = value;            value = newValue;            return oldValue;        }        public final boolean equals(Object o) {            if (o == this)                return true;            if (o instanceof Map.Entry) {                Map.Entry<?,?> e = (Map.Entry<?,?>)o;                if (Objects.equals(key, e.getKey()) &&                    Objects.equals(value, e.getValue()))                    return true;            }            return false;        }    }

hashMap中如何计算hash值

static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

如果key==null那么就将键值对存入索引为0的桶内，如果不为空则计算key的hashcode值，将h右移16位进行异或运算得到hash值。
为什么要右移16位？
其实是为了减少碰撞，进一步降低hash冲突的几率。int类型的数值是4个字节的，右移16位异或可以同时保留高16位于低16位的特征
为什么要异或运算？
首先将高16位无符号右移16位与低十六位做异或运算。如果不这样做，而是直接做&运算那么高十六位所代表的部分特征就可能被丢失将高十六位无符号右移之后与低十六位做异或运算使得高十六位的特征与低十六位的特征进行了混合得到的新的数值中就高位与低位的信息都被保留了，而在这里采用异或运算而不采用& ，| 运算的原因是异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢

if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);

总结：
(n-1)&hash判断元素存放的位置，n-1等于数组的长度，与运算相当于取余运算(计算速度大于取余运算)
假如不做右移运算，那么hash仅是最后四位和1111运算(假如数组长度为16)那么hash高位的信息就会全部丢失（比如如果有多个key.hashcode最后四位都是0000那么就会全部存储在索引为0的桶中产生碰撞），如果右移16位就会将高位的信息与低位的16位异或运算，保留了高位与低位的特征更能体现key.hashcode的特征，降低冲突的概率。
主要目的：上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分布，减少哈希碰撞，提升hashmap的运行效率

Java中hashMap为什么无符号移动16位，为什么要异或运算）

相关推荐