J58.82.224.67ava中的HashMap的实现原理高防服务器租用香港服务器

高防服务器IDC

J58.82.224.67ava中的HashMap的实现原理高防服务器租用香港服务器

需要咨询以下联系方式
联系人：銳輝（香港）科技 敏敏
扣扣：3007425289/2853898501
电话：18316411879

hashCode是什么
哈希表

hash表也称散列表(Hash table)，是根据关键码值(Key value)而注解进行访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数也叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数f(key)为哈希(Hash)函数。
简单的理解就是：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
具有快速查找和插入操作的优点。
hashCode

hashCode通过hash函数计算得到，hashCode就是在hash表中有对应的位置
每个对象都有hashCode，通过对象的物理地址转换为一个整数，将整数通过hash计算就可以得到hashCode
hachCode 有什么作用
hashCode的存在主要是用于查找快捷性，如HashTable，HashMap等。hashCode是用来散列存储结构中确定对象的存储地址。
如果两个对象相同，就适用于equals(java.lang.Object)方法，那么这个两个对象的hashCode一定要相同。
如果对象的equals方法被重写，那么对象的hashCode也要尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违法上面提到的第2点。
两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object)方法，只能够说明这两个对象在散列存储结果中。
如何判断集合中是否已经存在该对象了

​        首先想到的方法就是调用equals()方法。但是如果集合中已经存在大量的数据或者更多的数据，采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新得对象时，先调用这个对象得hashCode方法，得到对应得hashCode值，实际上在HashMap得具体实现中会一个表保存已经存进去得对象得hashCode值，如果table中没有该hashCode的值，它就可以存进去，不用再进行任何比较了。如果存在该hashCode值，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其他的地址，所以这里存在一个冲突的解决问题，这样依赖实际调用equals方法的次数就大大降低了。

​        这也就解释了为什么equals()相等，则hashCode()必须相等，如果两个对象equals()相等，则它们在哈希表(如HashSet，HashMap等)中应该出现一次。如果hashCode()不相等，那么他们会被散列到哈希表的不同位置，哈希表中出现了不止一次。

​        hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。

hashCode() 和 equals()
​        Java的基类Object中的equals()方法用于判断两个对象是否相等，hashCode()方法用于计算对象的哈希码。equals()和hashCode都不是final方法，都可以被重写。

hashCode()方法
Object类中的hashCode()方法的声明如下：

public native int hashCode();
1
可以看出，hashCode()是一个native方法，而且返回值类型是整形。实际上，该native方法将对象在内存中地址最为哈希码返回，可以保证不同对象的返回值不同。

与equals()方法类型，hashCode()方法可以被重写。JDK中对hashCode()方法的作用，以及实现时的注意的说明

hashCode()在哈希表中起作用，如java.util.HashMap。
如果对象在equals()中使用的信息都没有改变，那么hashCode()值始终不变。
如果两个对象使用equals()方法判断为相等，则hashCode()方法也应该相等。
如果两个对象使用equals()方法判断为不相等，则不要求hashCode()也必须不相等。但是开发人员应该认识到，不相等的对象产生不相同的hashCode可以提高哈希表的性能。
重写hashCode()的原则

如果重写了equals()方法，检查条件"两个对象使用equals()方法判断为相等，则hashCode()方法也应该相等"是否相等，如果不成立，则重写hashCode()方法。
hashCode()方法不能太过于简单，否则哈希冲突过多。
hashCode()方法不能太过复杂，否则计算复杂度过高，影响性能。
equals方法
equals()和==

==用于比较引用和比较基本数据类型时具有不同的功能：

​        比较基本数据类型，如果两个值相同，结果为true。

​        在比较引用时，如果引用指向内存中的同一对象，结果为true。

equals()作为方法，实现对象的比较。由于运算符不允许我们进行覆盖，也就是说它限制了我们的表达。因此我们重写equals()方法，达到比较对象的内容是否相同的目的。而通过==运算符是做不到的。

object类的equals()方法的比较规则为：如果两个对象的类型一致，并且内容一致，则返回true。

String str1 = new String("abc");
String str2 = new String("abc");
System.out.print(str == str2);                // false
System.out.print(str.equals(str2)); // true

HashMap中的hash()函数
HashMap中没有使用KV中原有的hash值。在HashMap的put，get操作时也未使用K中原有的hash值，而使用了hash()方法。

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

这段代码类似作用是为了增加hashCode的随机性。

key.hashCode()的作用返回键值key所属性类型自带的hashCode，返回的类型是int，如果直接拿散列值作为下表访问HashMap的主数组的话，考虑到int类型值得方位[ -231，231-1 ]，虽然只要hash表映射比较松散得话，碰撞几率很小，但是映射空间太大，内存放不下，所以先做对数组得长度取模运算，得到得余数才能用来访问数组下标。

HashMap的resize()
​        当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高(因为数组的长度是固定的)，所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，想想我们的"均摊"原理，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数组必须重新计算其在新数组中的位置，并放进去，这就是resize。

数组初始化以及数组元素个数大于阈值时进行扩容操作，一部分索引会增加原长度大小的长度(用到了高位1)，一部分仍保证原索引(高位为0)。

final Node<K,V>[] resize() {
            // 将旧数组进行保存
        Node<K,V>[] oldTab = table;
            // 保存旧数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 保存旧数组的阈值
        int oldThr = threshold;
            // 定义新的长度和阈值
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 数组以及达到最大容量，直接返回
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 新数组长度为旧数组长度*2
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 阈值同样*2
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults，默认的初始化操作
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
            // 将新的阈值付给成员变量
        threshold = newThr;
            // 创建一个新的数组，大小为newCap
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
            // 将旧数组元素放入到新数组中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果当前索引只有一个节点
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {