• 哈希表（HashTable)概述

　　哈希表本质上一种顺序结构的数组。通过设定的散列函数，将关键字映射到一个有限的地址区间（如数组的角标），

然后将value存储在地址中。

　　注意区分哈希算法 和 哈希表的算法

　　哈希算法

　　密码学基础，比较常用的有MD5和SHA，就是不可逆和无冲突。

　　所谓不可逆，就是当你知道x的HASH值，无法求出x；

　　所谓无冲突，就是当你知道x，无法求出一个y， 使x与y的HASH值相同。

　　将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。

　　哈希值是一段数据唯一且极其紧凑的数值表示形式。

　

　　HashCode

　　hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值

 

• 散列函数（根据关键字 ，以数据均匀分布在定长数组中为目的的函数）

1. 除法散列  （key mod TableSize） 
   1. 取模运算，表的Size最好为素数。
   2. 效率比较低。
   3. 当key是字符串的时候，一般是把字符串中子粗的ASCII码相加
2. 霍纳散列  （字符串）
   1. 霍纳规则是采用最少的乘法运算策略，求多项式A(x) = anxn+ an-1xn-1+...+ a1x + a0在x0处的值，该规则是A(x0)=(...((anx0+ an-1)x0+...+ a1)x0+ a0)
   2. ∑ (KeySize - 1) Key[KeySize - i -1]32`2
3. Fibonacci散列（0，1，1，2，3，5，8...）
   1. 对于16位整数而言，这个乘数是40503

      对于32位整数而言，这个乘数是2654435769
      对于64位整数而言，这个乘数是11400714819323198485

   2. index = (value * 2654435769) >> 28
   3. Fibnacci散列是平方散列法的优化，解决了数据过大导致的内存溢出，利用了黄金分割数（一知半解0.0) 乘法和位运算比取模运算效率高

　     4.JDK 1.8 HashMap中的散列算法。

 

 

　　　　1.hashCode()  //调用本地方法生成int类型的hashCode

public native int hashCode()

　　　　2.hash()  //java 8 中对哈希值的优化函数，为了防止某些不太好的散列函数。

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

 　　　 3.indexFor()  哈希值和数组长度-1进行&操作，得到数组角标。

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

 

　　　　

• 散列冲突（拉链法，开放定址法，再散列）
• 扩展哈希表
• Java-HashMap源码分析
  //哈希表内部的HashMapEntry,是一个节点类型 static class HashMapEntry
         
           implements Entry
          
            {        final K key;      //唯一关键码key        V value;          //数据域        final int hash;  //散列值f(key)        HashMapEntry
           
             next;   //指针域        HashMapEntry(K key, V value, int hash, HashMapEntry
            
              next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }        public final K getKey() {            return key;        }        public final V getValue() {            return value;        }        public final V setValue(V value) {            V oldValue = this.value;            this.value = value;            return oldValue;        }       //重写了equals方法，首先比较类型，然后比较key,然后比较value        @Override public final boolean equals(Object o) {            if (!(o instanceof Entry)) {                return false;            }            Entry
              e = (Entry
             ) o;            return Objects.equal(e.getKey(), key)                    && Objects.equal(e.getValue(), value);        }        //hashCode方法        @Override public final int hashCode() {            return (key == null ? 0 : key.hashCode()) ^                    (value == null ? 0 : value.hashCode());        }        @Override public final String toString() {            return key + "=" + value;        }    }
            
           
          
         
  1 //HashMap的put方法  2  3 @Override public V put(K key, V value) { 4         if (key == null) { 5             return putValueForNullKey(value);  //key为空则在同一位置put值 6         } 7  8         // 优化key.hashCode()，生成哈希值hash 9         int hash = Collections.secondaryHash(key);  10         HashMapEntry
         
          [] tab = table;11         int index = hash & (tab.length - 1);   //获取数组角标12         //如果key值一样，则覆盖数据      13         for (HashMapEntry
          
            e = tab[index]; e != null; e = e.next) {14             if (e.hash == hash && key.equals(e.key)) {15                 preModify(e);16                 V oldValue = e.value;17                 e.value = value;18                 return oldValue;19             }20         }21 22         // No entry for (non-null) key is present; create one23         modCount++;24         if (size++ > threshold) {25             tab = doubleCapacity();26             index = hash & (tab.length - 1);27         }28          //在数组中链表头部加入新节点29         addNewEntry(key, value, hash, index);30         return null;31     }