前言

哈希(Hash)或者说散列表，它是一种基础数据结构。Hash 表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，但它又是是数组和链表的基础上演化而来，既具有数组的有点，又具有链表的有点。能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。应用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

哈希表定义

哈希表（hash table，也叫散列表），是根据键（key）直接访问访问在内存储存位置的数据结构。

哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对。根据下标index从数组中取value。关键是如何获取index，这就需要一个固定的函数（哈希函数），将key转换成index。不论哈希函数设计的如何完美，都可能出现不同的key经过hash处理后得到相同的hash值，这时候就需要处理哈希冲突。

哈希表优缺点

优点 ：哈希表可以提供快速的操作。

缺点 ：哈希表通常是基于数组的，数组创建后难于扩展。也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项。

哈希表，典型的【空间换时间】

它是如何实现高效处理数据的? put("kwok", 121); put("steve",23242 ); put("jobs", 2132); 添加、搜索、删除的流程都是类似的

1. 利用哈希函数生成key对应的index【O(1)】

2. 根据index操作定位数组元素【O(1)】

image-20200422160109703.png

哈希函数

哈希表中哈希函数的实现步骤大概如下

1. 先生成key的哈希值(必须是整数)

2. 再让key的哈希值跟数组的大小进行相关运算，生成一个索引值

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

为了提高效率，可以使用 & 位运算取代 % 运算【前提:将数组的长度设计为 2 的幂(2n)】

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

良好的哈希函数
让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能

如何生成key的哈希值

key 的常见种类可能有
整数、浮点数、字符串、自定义对象
不同种类的 key，哈希值的生成方式不一样，但目标是一致的
尽量让每个 key 的哈希值是唯一的
尽量让 key 的所有信息参与运算

在Java中，HashMap 的 key 必须实现 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 将存储的二进制格式转为整数值

/**
 * 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 混合计算出 32bit 的哈希值
充分利用所有信息计算出哈希值

image-20200422171256111.png

字符串hash 值

整数 5489 是如何计算出来的?
5*10^3 +4*10^2 +8*10^1 +9*10^0
字符串是由若干个字符组成的
比如字符串 jack，由 s、t、e、v、e 五个字符组成(字符的本质就是一个整数) 因此，steve的哈希值可以表示为s*n^4 + t*n^3 +e*n^2 +v*n^1 +e*n^0

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 是一个奇素数，JVM会将 31 * i 优化成 (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;
}

自定义对象的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: "北京市海淀区",
      ID: "2011234010303",
   }
   fmt.Println(s1.hashCode())

}

自定义对象作为key

自定义对象作为 key，最好同时重写 hashCode 、equals 方法
equals :用以判断 2 个 key 是否为同一个 key

1. 自反性:对于任何非null 的x，x.equals(x)必须返回true
2. 对称性:对于任何非 null 的 x、y，如果 y.equals(x) 返回 true，x.equals(y) 必须返回 true
3. 传递性:对于任何非 null 的 x、y、z，如果 x.equals(y)、y.equals(z) 返回 true，那么x.equals(z) 必须 返回 true
4. 一致性:对于任何非 null 的 x、y，只要 equals 的比较操作在对象中所用的信息没有被修改，多次调用 x.equals(y) 就会一致地返回 true，或者一致地返回 false

• 对于任何非 null 的 x，x.equals(null) 必须返回 false
• hashCode :必须保证 equals 为 true 的 2 个 key 的哈希值一样
• 反过来 hashCode 相等的 key，不一定 equals 为 true

不重写 hashCode 方法只重写 equals 会有什么后果?
可能会导致 2 个 equals 为 true 的 key 同时存在哈希表中

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

安卓中哈希值使用（主要是讲解java 中hash map 源码）待续