哈希（Hash）相关---Java中的Hash机制（HashMap、HashSet及对其源码解析

-----------------equals()和hashCode()-------------
如何像把自定义的类和基于散列的集合类结构一起工作是，该类的equals()和hashCode()实现就显得尤为重要。
在改写equals方法的时候应该符合java.lang.Object的规范：
1.自反性：x.equals(x)一定为true；
2.对称性：由x.equals(y)为true，则必有y.equals(x)为true；
3.传递性：如果x.equals(y)为true并且y.equals(z)为true，则x.equals(z)为true必成立；
4.对于任意非空引用x，x.equals(null)一定返回false；

对应hashCode()应该符合java.lang.Object的规范：
1.在一个应用程序执行期间，如果一个对象的equals()作比较所用到的信息没有被修改的话，那么对象调用hashCode()

多次，它必须返回同一个整数。（在同一应用程序多次执行的过程中，这个整数可以不同。）
2.如果两个对象根据equals()方法相等，那么调用这两个对象中任一个对象hashCode()方法必须产生相同的整数结果。
3.如果两个对象根据equals()方法是不相等的，那么调用这两个对象的hashCode()方法，不要求必须产生不同的整数结

果。
一个散列函数应该把一个集合中不相等的实例均匀地分布到所有可能的散列值上。
一般的hashCode()可以这样按照如下的方法定义：
1.定义int result=17；（17，是一个某个非零的整数，可以根据需要任选）
2.对于对象中每一个关键域f（指equals方法中考虑到的每一个域），执行如下步骤：
  a.为该域计算int类型的散列码c：
     i.如果该域是boolean类型，则，计算(f?0:1);
    ii.如果该域是byte、char、short或int类型，则计算(int)f
   iii.如果该域是long类型，则计算(int)(f^(f>>>32));(其中>>>表示无符号右移位)
    iv.如果该域是float类型，则计算Folat.floatToIntBits(f);
     v.如果该域是double类型，则计算Double.doubleToLongBits(f)得到一个long类型的值，然后按照步骤iii对long类型数值计算散列值。
    vi.如果该域是一个对象引用，并且该类的equals方法通过递归调用equals的方式来比较这个域， 则同样对这个域递归调用hashCode。

       如果要求一个更为复杂的比较，则为这个域计算一个“规范表示”然后针对该范式表示调用hashCode，如果该域的值为null，则返回0.
   vii.如果该域是一个数组，则把每一个元素当做单独的域来处理。也就是说，递归的应用上述规则  ，对每个重要的元素计算散列码，

         然后根据b中的做法把这些散列值组合起来。

  b.按照下面的公式，把步骤a中计算得到的散列码c组合到result中：
       result=37*result+c；
3.返回result；

4.写完了hashCode方法之后，检测“是否相等的实例具有相等的散列码”，如果不是，查找修正。

在计算hashCode时应注意：在equals方法中没有被考虑到的域都要排除在外；域中的冗余值也可不用考虑；

------------------------------------------
注意：String对象有个特点：如果程序中有多个String对象，都包含相同的字符串序列，那么这些String对象都映射到同一块内存区域。所以，如String s1=new String("hello");String s2=new String("hello") ;两个对象实例虽然是独立的，但是对它们使用hashCode()应该生成同样的结果。对于String而言，hashCode明显基于String的内容。
--------------------------------------------
--------------java中经典Hash实现-HashMap和HashSet----（源码解析）-----------------------------------------

java.util.HashMap<K,V>主要是用数组来存储数据，采用链表的方式解决key散列后产生的冲突。

public class HashMap<K,V>    extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable
{

    /**
     * 数组table默认初始容量，必须为2的幂，即2^p

     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 数组table最大容量，必须为2^p<= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 负载因子=可能的key的个数/存储容量

     * 默认加载因子，加载因子是一个比例，当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容

     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 这就是map的主要存储结构，其长度是2^p.
     */
    transient Entry[] table;

    /**
     * 在map中存储的键值对的个数

     */
    transient int size;

    /**
     * 当实际数据大小超过threshold时，HashMap会将容量扩容，threshold＝容量*加载因子    

     */
    int threshold;

    /**
     * 负载因子

     * @serial
     */
    final float loadFactor;

    /**
     * modCount就是Map改变的次数，声明为volatile，保证线程之间修改的可见性；

     */
    transient volatile int modCount;

..,

-------------

transient Entry[] table;

Entry就是HashMap存储的数据:

static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;
        V value;
        Entry<K,V> next;//就是通过这个引用实现冲突时的链式存储结构的
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
     V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

-----------------------------------------------

HashMap的初始过程

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
其中HashMap(int initialCapacity, float loadFactor)的实现：

  

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;

      //通过传入的initialCapacity，找到一个比它大的最小的2^p，作为真正的容量capacity .例如给定 initialCapacity 为 14，那么该 HashMap 的实际容量就是 16。
        while (capacity < initialCapacity){

            capacity <<= 1;

        }
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];//初始化存储数组
        init();
    }

table 的实质就是一个数组，一个长度为 capacity 的数组。

对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。


-------------------

HashMap如何哈希：

HashMap并不是直接将对象的hashcode作为哈希值的，而是要把key的hashcode作一些运算以得到最终的哈希值，并且得到的哈希值也不是在数组中的位置，而是通过indexFor方法，将其转换成对于的数组下标。

int hash = hash(key.hashCode());

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 
int i = indexFor(hash, table.length);

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

当 length 总是 2 的倍数时，h & (length-1)将是一个非常巧妙的设计:由&运算符的性质（1&1=1，1&0=0）容易知道，这样的索引值总是位于table的数组索引之内。

------------------------------------

HashMap中put的操作：

public V put(K key, V value) 
{ 
         // 如果 key 为 null，调用 putForNullKey 方法进行处理
         if (key == null) 
           return putForNullKey(value); 
         // 根据 key 的 keyCode 计算 Hash 值
         int hash = hash(key.hashCode()); 
        // 搜索指定 hash 值在对应 table 中的索引
         int i = indexFor(hash, table.length);
        // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素
       for (Entry<K,V> e = table[i]; e != null; e = e.next) 
        { 
          Object k; 
           // 找到指定 key 与需要放入的 key 相等（hash 值相同  通过 equals 比较放回 true）

          //也就是，如果找到了“相同的key",就替换掉原来的值，例如put(3,newValue),而替换掉3处原来的值oldValue，而对于的key是不变的
          if(e.hash == hash && ((k = e.key) == key || key.equals(k))) 
          { 
             V oldValue = e.value; 
             e.value = value; 
             e.recordAccess(this); 
             return oldValue; 
         } 
      } 
      // 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry 
       modCount++; 
      // 将 key、value 添加到 i 索引处
      addEntry(hash, key, value, i); 
      return null; 
} 

上述put方法调用了addEntry

addEntry的具体实现如下：

void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry Entry<K,V> e = table[bucketIndex]; // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry ，可以看到，table的bucketIndex处只 存储了最新的那个元素，而其他的元素都会以引用的形式保持到后继加进来的Entry中，也就是所，最后加入的元素总是排在第一个位置 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限就进行扩容 if (size++ >= threshold) // 把 table 对象的长度扩充到 2 倍。 resize(2 * table.length); }
系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序 Entry<K,V> e = null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。
--------------------------------

HashMap中扩容的resize方法的具体实现：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

重点是的 transfer方法

  

 void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); 
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

tranfer方法将所有的元素重新哈希，因为新的容量变大，所以每个元素的哈希值和位置都是不一样的，所以频繁扩容会带来性能的明显下降。
------------------------------------------

HashMap 的读取实现：

public V get(Object key) 
{ 
          // 如果 key 是 null，调用 getForNullKey 取出对应的 value 
         if (key == null) 
             return getForNullKey(); 
         // 根据该 key 的 hashCode 值计算它的 hash 码
         int hash = hash(key.hashCode()); 
       // 直接取出 table 数组中指定索引处的值，搜索该 Entry 链的下一个 Entr 
       for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) 

       { 
           Object k; 
              // 如果该 Entry 的 key 与被搜索 key 相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
                return e.value; 
        }  
      return null; 
  }

如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止。

-----正确使用HashMap应该注意的地方-----------------------------

1：不要在并发场景中使用HashMap（关于并发，可以考虑并发包中java.util.concurrent.ConcurrentHashMap，这个会在后继集合框架的介绍中专门解析）

       HashMap是线程不安全的，如果被多个线程共享的操作，将会引发不可预知的问题，据sun的说法，在扩容时，会引起链表的闭环，在get元素时，就会无限循环，后果是cpu100%。

2：如果数据大小是固定的，那么最好给HashMap设定一个合理的容量值

        根据上面的分析，HashMap的初始默认容量是16，默认加载因子是0.75，也就是说，如果采用HashMap的默认构造函数，当增加数据时，数据实际容量超过10*0.75=12时，HashMap就扩容，扩容带来一系列的运算，新建一个是原来容量2倍的数组，对原有元素全部重新哈希，如果你的数据有几千几万个，而用默认的HashMap构造函数，因为HashMap不断扩容，不断哈希，这样是非常消耗系统资源的。

----------------------------HashSet的实现---------------------

其实HashSet内部包含一个HashMap的引用，依赖于HashMap的实现， 两个集合在实现本质上是相同的。具体实现可以参考jdk的源码，这里不再赘述了。