前言

哈希(Hash)或者說散列表呼寸，它是一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)控妻。Hash 表是一種特殊的數(shù)據(jù)結(jié)構(gòu)鸥印，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別蹬音，但它又是是數(shù)組和鏈表的基礎(chǔ)上演化而來上煤，既具有數(shù)組的有點(diǎn)，又具有鏈表的有點(diǎn)著淆。能夠快速定位到想要查找的記錄劫狠，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來進(jìn)行查找。應(yīng)用了函數(shù)映射的思想將記錄的存儲(chǔ)位置與記錄的關(guān)鍵字關(guān)聯(lián)起來永部，從而能夠很快速地進(jìn)行查找独泞。

哈希表定義

哈希表（hash table，也叫散列表）苔埋，是根據(jù)鍵（key）直接訪問訪問在內(nèi)存儲(chǔ)存位置的數(shù)據(jù)結(jié)構(gòu)懦砂。

哈希表本質(zhì)是一個(gè)數(shù)組，數(shù)組中的每一個(gè)元素成為一個(gè)箱子组橄，箱子中存放的是鍵值對(duì)孕惜。根據(jù)下標(biāo)index從數(shù)組中取value。關(guān)鍵是如何獲取index晨炕，這就需要一個(gè)固定的函數(shù)（哈希函數(shù)），將key轉(zhuǎn)換成index毫炉。不論哈希函數(shù)設(shè)計(jì)的如何完美瓮栗，都可能出現(xiàn)不同的key經(jīng)過hash處理后得到相同的hash值，這時(shí)候就需要處理哈希沖突瞄勾。

哈希表優(yōu)缺點(diǎn)

優(yōu)點(diǎn) ：哈希表可以提供快速的操作费奸。

缺點(diǎn) ：哈希表通常是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展进陡。也沒有一種簡(jiǎn)便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數(shù)據(jù)項(xiàng)愿阐。

哈希表，典型的【空間換時(shí)間】

它是如何實(shí)現(xiàn)高效處理數(shù)據(jù)的? put("kwok", 121); put("steve",23242 ); put("jobs", 2132); 添加趾疚、搜索缨历、刪除的流程都是類似的

1. 利用哈希函數(shù)生成key對(duì)應(yīng)的index【O(1)】

2. 根據(jù)index操作定位數(shù)組元素【O(1)】

image-20200422160109703.png

哈希函數(shù)

哈希表中哈希函數(shù)的實(shí)現(xiàn)步驟大概如下

1. 先生成key的哈希值(必須是整數(shù))

2. 再讓key的哈希值跟數(shù)組的大小進(jìn)行相關(guān)運(yùn)算以蕴，生成一個(gè)索引值

func HashCode(key string) int  {
    return hashCode(key) % len(table)
}

為了提高效率，可以使用 & 位運(yùn)算取代 % 運(yùn)算【前提:將數(shù)組的長(zhǎng)度設(shè)計(jì)為 2 的冪(2n)】

func HashCode(key string) int  {
   return hashCode(key) & (len(table) -1)
}

良好的哈希函數(shù)
讓哈希值更加均勻分布 → 減少哈希沖突次數(shù) → 提升哈希表的性能

如何生成key的哈希值

key 的常見種類可能有
整數(shù)辛孵、浮點(diǎn)數(shù)丛肮、字符串、自定義對(duì)象
不同種類的 key魄缚，哈希值的生成方式不一樣宝与，但目標(biāo)是一致的
盡量讓每個(gè) key 的哈希值是唯一的
盡量讓 key 的所有信息參與運(yùn)算

在Java中，HashMap 的 key 必須實(shí)現(xiàn) hashCode冶匹、equals 方法习劫，也允許 key 為 null

Integer hash 值就是值的本身

/**
 * Returns a hash code for this {@code Integer}.
 *
 * @return  a hash code value for this object, equal to the
 *  primitive {@code int} value represented by this
 *  {@code Integer} object.
 */
@Override
public int hashCode() {
return Integer.hashCode(value);
}

Float 將存儲(chǔ)的二進(jìn)制格式轉(zhuǎn)為整數(shù)值

/**
 * Returns a hash code for this {@code Float} object. The
 * result is the integer bit representation, exactly as produced
 * by the method {@link #floatToIntBits(float)}, of the primitive
 * {@code float} value represented by this {@code Float}
 * object.
 *
 * @return a hash code value for this object.
 */
@Override
public int hashCode() {
return Float.hashCode(value);
}
/**
 * Returns a hash code for a {@code float} value; compatible with
 * {@code Float.hashCode()}.
 *
 * @param value the value to hash
 * @return a hash code value for a {@code float} value.
 * @since 1.8
 */
public static int hashCode(float value) {
return floatToIntBits(value);
}

double 和long 哈希值

/**
 * Returns a hash code for a {@code long} value; compatible with
 * {@code Long.hashCode()}.
 *
 * @param value the value to hash
 * @return a hash code value for a {@code long} value.
 * @since 1.8
 */
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}

/**
 * Returns a hash code for a {@code double} value; compatible with
 * {@code Double.hashCode()}.
 *
 * @param value the value to hash
 * @return a hash code value for a {@code double} value.
 * @since 1.8
 */
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}

>> 和 ^ 的作用是?
高32bit 和 低32bit 混合計(jì)算出 32bit 的哈希值
充分利用所有信息計(jì)算出哈希值

image-20200422171256111.png

字符串hash 值

整數(shù) 5489 是如何計(jì)算出來的?
5*10^3 +4*10^2 +8*10^1 +9*10^0
字符串是由若干個(gè)字符組成的
比如字符串 jack，由 s嚼隘、t诽里、e、v嗓蘑、e 五個(gè)字符組成(字符的本質(zhì)就是一個(gè)整數(shù)) 因此须肆，steve的哈希值可以表示為s*n^4 + t*n^3 +e*n^2 +v*n^1 +e*n^0，等價(jià)于[(j*n+a)

public int hashCode() {
    int h = hash;
    final int len = length();
    if (h == 0 && len > 0) {
        for (int i = 0; i < len; i++) {
            h = 31 * h + charAt(i);//31 是一個(gè)奇素?cái)?shù)，JVM會(huì)將 31 * i 優(yōu)化成 (i << 5) – i
        }
        hash = h;
    }
    return h;
}
public int hashCode() {
    int h = hash;
    final int len = length();
    if (h == 0 && len > 0) {
        for (int i = 0; i < len; i++) {
            h = (h << 5) -h  + charAt(i);
        }
        hash = h;
    }
    return h;
}

自定義對(duì)象的hash值

package main

import "fmt"

type MyString string
type MyInt int
type Student struct {
   Name    MyString
   Age     MyInt
   ID      MyString
   Address MyString
}

func (s MyString) hashCode() int {
   h := 0
   for _, c := range string(s) {
      h = (h << 16) - h + int(c)
   }
   return h
}

func (i MyInt) hashCode() int {
   return int(i)
}
func (s Student) hashCode() int {
   hash := 0
   hash = (hash << 16) - hash + s.Name.hashCode()
   hash = (hash << 16) - hash + s.Age.hashCode()
   hash = (hash << 16) - hash + s.ID.hashCode()
   hash = (hash << 16) - hash + s.Address.hashCode()
   return hash
}
func main() {
   s1 := Student{
      Name: "steve",
      Age: 23,
      Address: "北京市海淀區(qū)",
      ID: "2011234010303",
   }
   fmt.Println(s1.hashCode())

}

自定義對(duì)象作為key

自定義對(duì)象作為 key蚀狰，最好同時(shí)重寫 hashCode 借卧、equals 方法
equals :用以判斷 2 個(gè) key 是否為同一個(gè) key

1. 自反性:對(duì)于任何非null 的x，x.equals(x)必須返回true
2. 對(duì)稱性:對(duì)于任何非 null 的 x拒贱、y，如果 y.equals(x) 返回 true佛嬉，x.equals(y) 必須返回 true
3. 傳遞性:對(duì)于任何非 null 的 x逻澳、y、z暖呕，如果 x.equals(y)斜做、y.equals(z) 返回 true，那么x.equals(z) 必須 返回 true
4. 一致性:對(duì)于任何非 null 的 x湾揽、y瓤逼，只要 equals 的比較操作在對(duì)象中所用的信息沒有被修改，多次調(diào)用 x.equals(y) 就會(huì)一致地返回 true库物，或者一致地返回 false

• 對(duì)于任何非 null 的 x霸旗，x.equals(null) 必須返回 false
• hashCode :必須保證 equals 為 true 的 2 個(gè) key 的哈希值一樣
• 反過來 hashCode 相等的 key，不一定 equals 為 true

不重寫 hashCode 方法只重寫 equals 會(huì)有什么后果?
可能會(huì)導(dǎo)致 2 個(gè) equals 為 true 的 key 同時(shí)存在哈希表中

iOS 中的哈希值使用 （- (BOOL)isEqual:(id)object; @property** (readonly) NSUInteger hash; ） 待續(xù)

安卓中哈希值使用（主要是講解java 中hash map 源碼）待續(xù)