基础算法汇总之哈希表

一. 什么是哈希表

哈希表也叫做散列表，是一种可以根据关键key值直接访问的数据结构；简单说就是把关键的key值映射到数组中一个位置来访问记录，这样可以加快反应速度。

这里面计算映射方法叫做​​散列函数​​​也叫做​​哈希（hash函数）​​​，存放记录的数组叫做​​散列表​​。是一种典型的空间换时间的策略。

这样当有一个数据来需要查询的时候，先通过散列函数计算出对应位置，在通过计算出位置的去查找，这样比直接查询所有数据速度块的。但是也需要注意这里的散列函数就要求效率要高。

二. 哈希函数

2.1. 简介

哈希函数也叫散列函数，它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）。【引用文章：​​https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html​​】

简单来说：哈希函数就是根据key计算出应哈希表上该存储的位置。

2.2. 常用方法

常见的几种哈希函数（散列函数）构造方法：

• 直接定址法：取关键字或关键字的某个线性函数值为散列地址。例如以年龄为关键字的散列表
• 随机数法：选择一个随机函数，把关键字的随机函数值作为它的哈希值。通常用于关键字长度不等时采用此法构造哈希函数。
• 折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
• 平方取中法：先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
• 除留余数法（最常用的）：取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
• 数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。

2.3. 数据类型

在针对不同的数据类型应该使用不同的哈希函数。

2.3.1. 正整数

针对正整数最常用的方法是：除留余数法 。

这里选择大小为素数（也叫做质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数）​​M​​​的数组，对于任意正整数​​k​​​，计算​​k​​​除以​​M​​的余数。这样可以将键有效的散布在从0到M-1的范围之内。

如果M不实用素数的话，会导致散列值分布不均匀，无法包含所有信息。

2.3.2. 浮点数

如果键是0到1之间的实数，我们可以将它乘以M并四舍五入得到一个0到M-1之间的索引值。但是这个方法是有缺陷的，就是高位起了决定性作用，地位对于索引的值没有什么影响。解决方法就是将浮点数表示为二进制然后再使用除留余数法。

Java中的浮点数获取hashCode就是这样操作的。下面我们简单看一下Float的hashCode方法：

public static int hashCode(float value) {
    return floatToIntBits(value);
}

@HotSpotIntrinsicCandidate
public static int floatToIntBits(float value) {
    if (!isNaN(value)) {
        return floatToRawIntBits(value);
    }
    return 0x7fc00000;
}

@HotSpotIntrinsicCandidate
public static native int floatToRawIntBits(float value);

jdk源码：

/*
 * Find the bit pattern corresponding to a given float, NOT collapsing NaNs
 */
JNIEXPORT jint JNICALL
Java_java_lang_Float_floatToRawIntBits(JNIEnv *env, jclass unused, jfloat v)
{
    union {
        int i;
        float f;
    } u;
    u.f = (float)v;
    return (jint)u.i;
}

经过上面的转换就可以将一个浮点数转为一个整数，这样在使用除留余数法，就比较合适了。

2.3.3. 字符串

字符串也可以使用除留余数法进行处理，这里可以将字符串看作一个大的整数即可。

接着看一个Jdk中String的hashCode方法：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

// StringLatin1.hashCode
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        // byte转int与上0xff的原因？ 
        h = 31 * h + (v & 0xff);
    }
    return h;
}

很简单Java中会遍历byte[]数组，每个字符对应的码值执行：​​h = 31 * h + (v & 0xff)​​。

至于为什么​​31*h​​​，可以参看​​stackoverflow​​的帖子。

这时候还需要注意String的hashCode函数产生的值会产生负值，取模或者取余作为数组的下标的时候会数组越界。

那么这里就会出现疑问：为什么hashCode会出现负值？参看扩展！

2.3.4. 组合键

对于一种键拥有多种整型变量，可以和String一样将它们混合起来。如果查找的键是Date类型，就会含有多种整数域：day、mouth和year。那么哈希函数：

int hash = (((day * R + mouth ) % M) R +year) % M

这样仍然可以获得一个0到M-1范围之内的散列值

2.3.5. Java的hashCode

在Java中Object类是所有类的父类，这就是的Java中所有的数据类型都可以继承并返回一个init类型的hashCode()方法。并且每一种数据类型的hashCode()和equals()一致。

a.equals(b)   // true
a.hashCode() == b.hashCode()  // true

如果使用自定义的数据类型定义散列函数需要同时重写hashCode()和equals()两个方法。（hashCode相同，但是equals不一定相同， 具体参看扩展）

这里使用中需要数组的索引而不是一32位的整数，在使用中可以hashCode()和除留取余法结合产生一个0到M-1之间的整数：

public int hash(Key x) {
  // 与0x7fffffff 是为了将符号位屏蔽。将32位的整数变成一个非负整数
  return (x.hashCode() & 0x7fffffff) % M;
}

下面演示一个不错的自定义数据类型的hashCode重写（正常情况下重写hashCode说也需要重写equals）：

public class TestCode {

    private Integer age;

    private String name;

    private Boolean sex;

    @Override
    public boolean equals(Object o) {
        // ... 省略
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name, sex);
    }
}

这里借助了Java提供的工具类：Objects.hash去实现hashCode方法的重写，接着看一下这里面是如何运算的：

public static int hash(Object... values) {
        // 真正的计算hashCode值的方法
    return Arrays.hashCode(values);
}

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        // 获取每一个值的hashCode和31做运算
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

2.4. 什么是好的哈希函数？

在为一个数据类型实现一个对应的哈希函数，至于这个哈希函数评价标准有三项：

• 一致性：等价的键必然产生相同的散列值
• 高效性：计算简便
• 均匀性：均匀的散列所有的键

其实在Java中有工具类和hashCode函数就可以满足使用了。

三. 冲突处理

上一个部分讲的是如何将键通过散列函数转换为数组索引（散列值），但是如果遇到多个键对应同一个散列值的时候，这时候就需要解决冲突（碰撞），解决碰撞问题常见的有三种方法：

• 链地址法
• 开放地址法
• 线性探测法

3.1. 链地址法

链地址法的基本思想是，为每个 Hash 值建立一个单链表，当发生冲突时，将记录插入到链表中。下面用代码实现一下：

首先定义相关实体类：

// DataNode 链结点
type DataNode struct {
  key string    // 数据key - 用来生成散列值
  value string  // 数据value
  next *DataNode // 下一个数据的指针
}

// HashNode 索引数据结点
type HashNode struct {
  index int       // 索引值
  head  *DataNode // 链表头指针
  end   *DataNode // 链表尾指针
  size  int       // 链表中元素个数
}

// HashTable hash表
type HashTable struct {
  hash []HashNode // 散列表
  size int        // 表长
}

增加​​get​​​和​​put​​方法：

func (h *HashNode) Get(key string) string {
  p := h.head
  for p != nil {
    if p.key == key {
      return p.value
    }
    p = p.next
  }
  return ""
}

func (h *HashNode) Put(key, value string) {
  node := NewDataNode(key, value)
  if h.head == nil {
    h.head = node
    h.end = node
    h.size++
  } else {
    p, flag := h.head, false
    for p.next != nil {
      if p.key == key {
        p.value = value
        flag = true
        break
      }
      p = p.next
    }
    if !flag {
      p.next = node
      h.end = node
      h.size++
    }
  }
}

增加散列函数

func (h *HashTable) hashCode(key string) int {
  bytes := []byte(key)
  res := 0
  for i := 0; i < len(bytes); i++ {

    res = 31 * res + int(bytes[i] & 0xff)
  }
  return res % h.size
}

增加对外使用的Insert和Search方法：

func (h *HashTable) Insert(key, val string) {
  idx := h.hashCode(key)
  idxNode := h.hash[idx]
  idxNode.Put(key, val)
  h.hash[idx] = idxNode
}

func (h *HashTable) Search(key string) string {
  idx := h.hashCode(key)
  idxNode := h.hash[idx]
  return idxNode.Get(key)
}

这样一个简单的散列表就是实现了，但是像一些装载因子、重新哈希等一些功能并没有实现，在Java中最常用的HashMap就是一个很不错散列表的学习例子（之后会出一篇文章详细解释）。

3.2. 开放地址法

开放地址法会让所有输入的元素全部存放在哈希表里。这样哈希表的实现是不需要任何的链表来实现的。

基本原理：当插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法，去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。

关于再寻址的方法常见的有如下几种：

• 线性探测：这个会产生首次聚集问题
• 二次探测：这个会产生二次聚集问题
• 在哈希法：再哈希法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置，但是每次冲突都要重新哈希，计算时间增加。

这里重点说一下线性探测法的具体实现，主要聚焦插入、删除、搜索和扩容（缩容）操作。

3.2.1. 基础信息

定义节点数据，实现ToString和构造方法：

// Node 结点数据
type Node struct {
  data int
  status bool // 标识是否删除
}

// ToString 输出结点信息
func (l *Node) ToString() {
  fmt.Printf("结点: [key:%d]\n", l.data)
}

// NewNode 创建结点
func NewNode(key int) *Node {
  return &Node{
    data: key,
    status: true,
  }
}

哈希表定义：

// HashTable 哈希表
type HashTable struct {
  node []*Node
  size int
  num int
}

// NewHashTable 创建哈希表
func NewHashTable(size int) *HashTable {
  return &HashTable{
    node: make([]*Node, size),
    size: size,
    num: 0,
  }
}

// Println 输出hash表中内容
func (h *HashTable) Println() {
  fmt.Print("哈希表内容：[")
  for _, item := range h.node {
    if item != nil && item.status {
      fmt.Printf("%d\t", item.data)
    } else {
      fmt.Printf("%s\t", "*")
    }
  }
  fmt.Print("]\n")
}

3.2.2. 插入

插入流程：

• 插入元素3，计算插入下标：3%8=3，将元素3插入下标为3的位置；
• 插入元素6，计算插入下标：6%8=6，将元素6插入下标为6的位置；
• 插入元素14，计算插入下标：14%8=6，可以得到将插入14元素到6的位置，但是发现6位置已经存在元素，接着查找下一个位置，发现下标为7的位置是空的，然后将元素插入7的位置；
• 插入元素30，计算下标：30%8=6，可以得到将会把30的元素插入到6的位置，但是发现6的位置存在元素，查找下一个位置发现7的位置也存在元素，此时考虑从0开始，发现0位置没有元素，则将30元素插入到0的位置。

插入流程如下图：

代码实现：

// Insert 插入数据
func (h *HashTable) Insert(data int) {
  // 判断是否需要扩容
  if h.num >= h.size / 2 {
    h.resize(2 * h.size)
  }
  // 计算hash值
  code := data % h.size
  for h.node[code] != nil && h.node[code].status {
    // 如果存在相同的直接结束
    if h.node[code].data == data {
      return
    }
    code = (code + 1) % h.size
  }
  // 插入数据
  h.node[code] = NewNode(data)
  h.num++
}

这里需要注意扩容。后面会介绍！

测试代码：

func TestHashTable_Insert(t *testing.T) {

  hashTable := NewHashTable(8)

  hashTable.Insert(3)
  hashTable.Insert(6)
  hashTable.Insert(14)
  hashTable.Insert(30)

  hashTable.Println() // 哈希表内容：[30  *  *  3  *  *  6  14  ]
}

3.2.3. 搜索

查找数据流程如下：

查询数据3，先计算哈希值为3，从下标3位置开始遍历HashTable，发现3位置的元素和查询数据相同并且非删除状态，说明找到并返回；

查询数据30，计算哈希值为6，从下标6位置开始遍历HashTable，发现6位置的元素与查询的元素不同；接着查询下一个位置的元素14也和查询的元素30不同；此时已经到了数组的尾，需要折回数组头，发现0位置的元素和查询元素相同并且非删除状态，说明找到并返回；

假如在0位置的元素也不相同，那么就比较下一个位置的元素，但是发现下一个位置的元素是nil或者是删除状态，说明没有要查找的元素，直接返回nil。

// Find 查询数据
func (h *HashTable) Find(data int) *Node {
  code := data % h.size
  for h.node[code] != nil && h.node[code].status {
    if h.node[code].data == data {
      return h.node[code]
    }
    code = (code + 1) % h.size
  }
  return nil
}

测试代码：

func TestHashTable_Find(t *testing.T) {
  hashTable := NewHashTable(8)

  hashTable.Insert(3)
  hashTable.Insert(6)
  hashTable.Insert(14)
  hashTable.Insert(30)

  hashTable.Println() // 哈希表内容：[30  *  *  3  *  *  6  14  ]

  hashTable.Find(30).ToString()  // 结点: [key:30]
  hashTable.Find(3).ToString()   // 结点: [key:3]
  hashTable.Find(14).ToString()  // 结点: [key:14]
}

3.2.4. 删除

删除哈希表中的元素，如果没有hash冲突元素，直接将节点置为nil或者将status设置false就可以删除，如下图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-maZdkHiv-1636516946742)(image/image_3.png)]

另外一种是删除针对有哈希冲突的元素，再删除的时候，需要将剩余的元素重置位置，防止删除之后无法找到，如下图：下标为6的元素有：6,14,30三个，当删除14之后，如果不重置30，在查找的时候将无法找到30这个元素。

重置的方法也很简单，就是删除元素之后hash值相同（data % 8）的位置移动于填补因为删除元素之后导致的空白位置。

代码实现：

// Delete 删除数据
func (h *HashTable) Delete(data int) bool {
  code, delFlag := data % h.size, false
  // 查找数据，并且删除
  for h.node[code] != nil && h.node[code].status {
    if h.node[code].data == data {
      h.node[code].status = false
      h.num--
      delFlag = true
      break
    }
    code = (code + 1) % h.size
  }

  // 如果没有找到数据，说明没有找到数据，直接返回
  if !delFlag {
    return delFlag
  } else {
    // 说明找到数据，并且删除掉了

    // 判断是否需要缩容，缩容的话就不需要重新索引
    if h.num > 0 && h.num == h.size / 8 {
      h.resize(h.size / 2)
      return delFlag
    }

    // 如果不缩容，就需要重新调整位置
    // 记录删除元素的位置和下个元素的位置
    curr, next := code % h.size, (code + 1) % h.size
    // 遍历next位置的元素不为空
    for h.node[next] != nil && h.node[next].status {
      // 如果next的下标和删除元素的hash值相同
      if h.node[next].data % h.size == data % h.size {
        // 移动值，并将next位置元素设置为也删除状态
        h.node[curr].data = h.node[next].data
        h.node[curr].status = true
        h.node[next].status = false
        // next指向下一个hash位置，curr指向next的位置
        curr, next = next, (next + 1) % h.size
      } else {
        // 没有找到的话，只移动next的指向
        next = (next + 1) % h.size
      }
    }
    return delFlag
  }
}

测试代码：

func TestHashTable_Delete(t *testing.T) {

  hashTable := NewHashTable(8)

  hashTable.Insert(3)
  hashTable.Insert(6)
  hashTable.Insert(14)
  hashTable.Insert(30)
  hashTable.Insert(11)
  hashTable.Insert(46)
  hashTable.Insert(1)
  hashTable.Println() // 哈希表内容：[46  1  *  3  *  *  6  *  *  *  *  11  *  *  30  14  ]
  hashTable.Delete(14)
  hashTable.Println()  // 哈希表内容：[*  1  *  3  *  *  6  *  *  *  *  11  *  *  30  46  ]
  hashTable.Find(46).ToString()  // 结点: [key:46]
  hashTable.Find(1).ToString()  // 结点: [key:1]

  hashTable.Delete(1)
  hashTable.Delete(3)
  hashTable.Delete(30)
  hashTable.Println() // 哈希表内容：[*  *  *  *  *  *  6  *  *  *  *  11  *  *  46  *  ]
  hashTable.Find(46).ToString()  // 结点: [key:46]
  hashTable.Delete(11)
  hashTable.Println()  // 哈希表内容：[*  *  *  *  *  *  6  46  ]
  hashTable.Find(6).ToString()  // 结点: [key:6]

}

3.2.5. 扩容（缩容）

在插入元素之前判断是否需要扩容，在删除元素之后判断是否需要缩容，扩容/缩容就是重新hash，重新确定元素的位置。

具体代码如下：

// resize 扩容/缩容
func (h *HashTable) resize(newSize int) {
  newNodes := make([]*Node, newSize)
  for _, item := range h.node {
    if item != nil && item.status {
      idx := item.data % newSize
      for newNodes[idx] != nil && newNodes[idx].status {
        if newNodes[idx].data == item.data {
          break
        }
        idx = (idx + 1) % newSize
      }
      newNodes[idx] = item
    }
  }
  h.node = newNodes
  h.size = newSize
}

测试：

func TestHashTable_Resize(t *testing.T) {
  hashTable := NewHashTable(8)

  hashTable.Insert(3)
  hashTable.Insert(6)
  hashTable.Insert(14)
  hashTable.Insert(30)

  hashTable.Println() // 哈希表内容：[30  *  *  3  *  *  6  14  ]

  hashTable.Insert(11)

  hashTable.Println() // 哈希表内容：[*  *  *  3  *  *  6  *  *  *  *  11  *  *  30  14  ]
  hashTable.Find(14).ToString() // 结点: [key:14]
  hashTable.Find(30).ToString() // 结点: [key:30]
}

扩展一：浮点数的二进制表示

Java是在Jvm虚拟机上运行的，Jvm又是使用C/C++编写的，目前C/C++标准都按照IEEE制定的浮点数进行float和double计算。表示格式如下图：

先说浮点数之前，先说一下做计算机编码：原码、反码和补码。

都知道计算机只识别0和1；一个数在计算机中的二进制表示形式叫做这个数的机器数 ，机器数是带符号的，在最高位放符号（正数是0，负数是1）。

例如：+5 转为二进制是：0000 0101；-5转为二进制是：1000 0101

机器数第一位是符号位，在形式上并不等于真正的数值，所以将0000 0101 对应的+5叫做0000 0101的真值 。

原码 ：加了符号位的二进制数（个人理解：机器数 == 原码； 真值 + 符号位 = 原码）

+5   ==>   0000 0101
-5   ==>   1000 0101

反码 ：正数反码就是其本身；负数的反码是在其原码的基础上，符号位不变，其余位取反

+5   ==>   0000 0101
-5   ==>   1111 1010

补码 ：正数的补码就是其本身；负数的补码是在其原码的基础上，符号位不变，其余位取反，再加1（相当于在反码的基础上+1）

+5   ==>   0000 0101
-5   ==>   1111 1011

那为啥需要反码和补码？假如我们需要计算​​6-3​​​的值，​​6-3​​​可以看作​​6 + (-3)​​先看如果用原码计算：

从上面可以知道，在进行​​1-1​​​的运算过程中，反码计算得到​​1111 1111​​​ 转为原码是​​1000 0000​​​，相当于​​-0​​​，虽然​​+0（0000 0000）​​​和​​-0（1000 0000）​​​是一样，但是带上符号位就没有任何意义了；反观通过补码计算等到的是​​0000 0000​​这个就很完美。

早期计算机​​CDC 6000​​​、​​LINC​​​、​​PDP-1​​等都是使用反码的。但是使用反码会出现如下的问题：

• 0的两种编码：​​0000 000​​ 和 ​​1000 0000​​；
• 反码减法计算规则较为复杂，需要增加计算机内部逻辑组件额外判断溢位，会影响计算效率；

后面反码的加减运算就慢慢换成了补码。从下面也可以看出为什么​​1000 0000​​​ 表示 ​​-128​​！

上面扯了一堆，为的是回忆一下计算机计算的一些基础，接着回归浮点数的表示问题！

十进制小数转二进制小数采用的乘2取整，顺序排序 的方法，如下图计算0.8125的二进制：

下面看一下​​double​​​类型​​38414.4​​的二进制表示：

现将数据分为整数部分（​​38414​​​）和小数部分（​​0.4​​），将这两部分转为二进制数

​​38414​​​[十进制] = ​​1001011000001110​​[二进制]

​​0.4​​​[十进制] = ​​0.01100110......​​​[二进制]，这里的​​0.4​​的二进制是永远算不完的（这也是浮点数精度问题）

这里我们只需要将整数部分的二进制位数加上小数部分的二进制位数够53位就可以了。

​​1001011000001110.0110101010101010101010101010101010101 = 38414.4​​，接着转为二进制的科学计数法：

​​1.0010110000011100110101010101010101010101010101010101 x 2^15​​，那么可以确定指数是15；舍去整数的1，将后面的小数作为尾数；

然后就可以去定阶码了，对于double的阶码是有符号位的，一共是11位，所以需要15 + 1023（1023是11位中10位的最大值） = 1038 = 10000001110。最后38414.4 是正数符号位0；将这三部分组合在一起就是38414.4的二进制：​​01000000 11100010 11000001 11001101 01010101 01010101 01010101 01010101​​，具体看下面示意图：

扩展二：HotSpotIntrinsicCandidate 注解

在​​JDK​​​中很多源码会被​​@HotSpotIntrinsicCandidate​​​注解，该注解在​​JDK 9​​中被引入。

被​​@HotSpotIntrinsicCandidate​​​标注的方法，在​​HotSpot​​​中都有一套高效的实现，该高效实现基于​​CPU​​​指令，运行时，​​HotSpot​​​维护的高效实现会替代​​JDK​​的源码实现，从而获得更高的效率。

如何查找native对应在jdk源码中的位置可以查看这篇文章：​​https://gorden5566.com/post/1027.html​​

扩展三：String压缩

​​Jdk9​​​的将​​String​​​的底层数据存储将​​char[]​​​变成了​​byte[]​​，并且Jdk9之后String支持两种编码格式：LATIN1（一个字节）和UTF16（2/4个字节）。

static final boolean COMPACT_STRINGS;

static {
    COMPACT_STRINGS = true;
}

并且通过​​COMPACT_STRINGS​​​控制是否开启​​String​​​的紧凑模式，默认是开启的，关闭通过：​​-XX:-CompactStrings​​参数。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

// StringLatin1.hashCode
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
} 

// StringLatin1.hashCode
public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

@HotSpotIntrinsicCandidate
// intrinsic performs no bounds checks
static char getChar(byte[] val, int index) {
    assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";
    index <<= 1;
    return (char)(((val[index++] & 0xff) << HI_BYTE_SHIFT) |
                  ((val[index]   & 0xff) << LO_BYTE_SHIFT));
}

public static int length(byte[] value) {
    return value.length >> 1;
}

扩展四：String的hashCode负值

先看String.hashCode的方法源码：

public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

这个代码很简答，但是会不会产生两个疑问：

• 如果字符串足够长，会不会导致数据溢出？
• 为什么要与上​​0xff​​？

下面挨个去解释这两个问题：

先演示int类型乘法溢出的情况：

public static void main(String[] args) {
    System.out.println("abcde".hashCode());   // 92599395
    System.out.println("abcdef".hashCode());  // -1424385949
}

这个值为什么会出现负值​​-1424385949​​​呢？这个问题在​​Java虚拟机说明书​​​中对这个问题做出过介绍：​​数据类型的变窄转换​​。

大体是这样：当Java结算结果超过int基本数据类型的最大范围时，会做默认的类型提升，中间结果作为long类型存放，返回时目标数据类型是int型不能容纳结果，于是将原来long类型的转为int类型，超出的部分全部丢弃，只去结果的32位。至于为什么会负数，这个是类型变窄之后符号位是1有关。下面用图演示一下：

接着在看一下为什么要与上​​0xff​​？

先看下面这个代码：

byte a = -127;
int b = a & 0xff; = 129

这还的从补码上面思考，​​-127​​​的补码是：​​1000 0001​​​，但是当byte转为int的时候会高24位上全都补1，那么在第二行：​​b = a & 0xff;​​​在计算的时间将byte转为int，byte是8位，int是32位，现在转为int，少了的24位Jvm会用1填充，那么现在-127的补码是：​​11111111 11111111 11111111 10000001​​​；当与上0xff的时候，补码就变成了：​​00000000 00000000 00000000 10000001​​​，这样就会和原来​​-127​​的补码一致。在计算机底层计算的时候只关心补码。

扩展五：hashCode和equals

这两个方法经常用总结一个吧！

equals作用：判断两个对象是否相等，默认实现是判断对象地址是否相同此时和​​==​​一样的。

public boolean equals(Object obj) {
    return (this == obj);
}

在重写equals()方法判断两个对象内容是否相等，下面看一下如何重写equals()方法：

public class TestCode {

    private Integer age;

    private String name;

    private Boolean sex;

    @Override
    public boolean equals(Object o) {
        // 判断地址相同
        if (this == o) {
            return true;
        }
        // class是否相同
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        // 对象属性内容是否相同
        TestCode testCode = (TestCode) o;
        return Objects.equals(age, testCode.age)
                && Objects.equals(name, testCode.name)
                && Objects.equals(sex, testCode.sex);
    }
}

hashCode()作用是获取散列码；返回一个int整数；只有在创建某个类的散列表（HashMap、HashTable和HashSet）时这个hashCode才会起作用，在散列表需要通过hashCode()获取对象的散列表，进而确认对象在散列表中的位置。

重写hashCode的可以使用Objects的工具类去实现hashCode方法：

public class TestCode {

    private Integer age;

    private String name;

    private Boolean sex;

    @Override
    public int hashCode() {
        return Objects.hash(age, name, sex);
    }
}

接着到这个方法里面查看是如何实现：

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

可以看到获取每个属性的hashCode，计算乘以31值。

这里需要注意，两个对象相等那么这两个对象的hashCode值一定相同；两个对象的hashCode相同但是这两个对象不一定相同（这就是哈希冲突）。

扩展六：HashMap、HashTable和HashSet

这几个都是集合类都是基于散列表，分析它们可以从如下几个点出发：

• 线程安全：HashTable是线程安全，HashMap和HashSet不是；
• 实现方式：HashMap基于拉链法的散列表，链过长会自动转为红黑树，HashSet底层采用HashMap实现的；
• 初始大小：HashTable初始大小是11，HashMap初始大小是16
• 空值：HashMap可以将空值作为key（一条：键不能重复）或者value（多条），HashTable不允许null值（键与值都不行）,HashSet多个null只会有一个null存在。
• 扩容方式：HashTable采用：​​(oldCapacity << 1) + 1​​，HashMap采用​​oldCap << 1​​
• 哈希值：HashTable直接使用对象的hashCode，而HashTable采用在对象的hashCode上还进行的处理变化；