有关HashCode以及相关知识

今天看了一些有关HashCode的博文，将网上相关的知识整理之后分享一下。

---

HashCode

什么是HashCode

HashCode 也即哈希码，是 Java对象 的一个特征码，用它来区分两个Java对象是否相同。
HashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。

为什么要用HashCode

1. 因为散列集合中不允许存在重复对象，当向集合中插入对象时，需要判别在集合中是否已经存在该对象，那么这个时候就需要用到HashCode。

2. 便于实现 散列存储。

散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。 -----<a herf="https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E5%AD%98%E5%82%A8%E6%96%B9%E6%B3%95/9663463">[百度百科]

以HashMap为例

先提一下 HashMap 中的indexFor()方法：

static int indexFor(int h, int length) { 
    return h & (length-1); 
}

indexFor()方法用于返回插入数据的位置。普通的Hash打散的算法都是mod表的长度，比如h%length,但是 HashMap 却用的是位运算。

因为 HashMap 的初始大小和扩容都是以2的次方来进行的，换句话说length-1换成二进制永远是全部为1，比如 length 为16，则 length-1 为 1111. 而我们知道，任何一个数与它对应的二进制位数上全为1的二进制数进行与运算就是它本身。（例：1001001 ^ 1111111 = 1001001）, 这样保证插入的数据存放在不同的位置，从而最小化哈希冲突，从而实现 散列存储。

再观察 HashMap 中的put()方法：

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
  
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

其主要思想便是：在键不为空时，根据键对象获取到散列码hash，然后通过散列码得到数组的下标i。在table[i]所表示的 Entry<k,v> 中进行迭代，通过equals()判断该键是否存在，如果存在，则用新的值更新旧的值，返回旧的值；否则将新的键值对添加到 HashMap 中。从这里可以看出，hashCode() 方法的存在是为了减少 equals() 方法的调用次数，从而提高程序效率。
　　这里我们需要注意到：hashCode() 并不需要总是能够返回唯一的标识码，但是 equals() 方法必须严格地判断两个对象是否相同。

• 注：
  这里贴出的 HashMap 的 put() 方法是网上找的，与我的 jdk1.8 里的内容不一致，但不影响理解。（原因是：JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间）
  在 jdk1.8 中 Entry<k,v> 是 Node<K,V> ，原理其实都一样，Node<K,V>是一个静态类，有键值对，还有 hash 和 next 属性。相当于实现了一个链表。
  函数里的 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;
   }
}

HashCode的生成

哈希码产生的依据：哈希码并不是完全唯一的，它是一种算法，让同一个类的对象按照自己不同的特征尽量的有不同的哈希码，但不表示不同的对象哈希码完全不同。也有相同的情况，看程序员如何写哈希码的算法。-----<a herf="https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E7%A0%81"> [百度百科]

同样以HashMap为例

HashMap类中的 hash() 方法:

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

在 Object 类中hashCode() 是一个native方法，意味着方法的实现和硬件平台有关，默认实现和虚拟机有关，对于有些JVM，hashCode()返回的是对象的地址，大多时候JVM根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，并返回。
而在 HashMap中，会调用 Key 所属类实现的 hashCode()方法获得 hashCode。

hash() 是一个返回int值的本地方法。当向一个容器(我们假设是HashMap)中插入一个对象时，怎样判断容器中是否已经存在该对象了呢？由于容器中的元素可能成千上万，使用equals()方法依次进行比较是非常低效的。散列的价值在于速度，它将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以使用它来存储键的信息（注意是键的信息，而非键本身）。我们希望在Map中保存数量不确定的值，但是如果键的数量被数组的容量限制了，该怎么办呢？
　　答案就是：数组不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码（hashcode），由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成。为解决数组容量被固定的问题，不同的键可以产生相同的下标，这种现象被称为哈希冲突（之前也有说过怎么最小化哈希冲突）。于是，在 HashMap 中查询一个值的过程是：先通过 hash() 计算待插入对象的散列码，然后使用散列码查询数组。对于冲突的处理，常常是通过外部链接，即数组并不直接保存值，而是保存相同 hashCode 的对象链表（之前提到的 Node<K,V>链表），然后依次对链表中的值进行线性查询，这部分查询自然会比较慢。但是，如果散列函数足够好的话，数组的每个位置就只有较少的值。因此，散列机制便可以快速地跳到数组的某个位置，只对很少的元素进行比较。这就是HashMap会如此快的原因。

在Java中，不同的对象有不同的HashCode的生成方法：

• Object类型

  Object类的 hashCode() 返回对象的内存地址经过处理后的结构，由于每个对象的内存地址都不一样，所以哈希码也不一样。

• String类型

  String类的 hashCode() 根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串所在的堆空间相同，返回的哈希码也相同。

  public int hashCode() {
      int h = hash;
      if (h == 0 && value.length > 0) {
          char val[] = value;
  
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
  }
  

  在String类中有 hashCode 的私有字段

  /** Cache the hash code for the string */
  private int hash; // Default to 0
  

  在第一次调用hashCode方法时，字符串的哈希值被计算并且赋值给hash字段，之后再调用hashCode方法便可以直接取hash字段返回。
  而计String类型计算 hashCode 的方法也比较简单：以31为权重，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

  • 题外话：为什么要选择31作为权重？

  "之所以选择值31是因为它是奇数素数。如果它是偶数，并且乘法溢出，则信息将丢失，因为2的乘法相当于移位。
  使用素数的优点不太清楚，但它是传统的。31的一个很好的特性是，可以用一个移位和一个减法来代替乘法，以获得更好的性能：31×i =（i < 5）- i。
  现代VMS自动完成这种优化。" -----参考<a herf="https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier">Stack Overflow
  - Integer类型
  Integer类就比较简单了，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100) , i1.hashCode 的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
  - HashMap
  java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

暂时先写到这吧~~后序如果还有补充内容的话会继续更新。如有错误，还请指正。