《数据结构与算法》总结（六）哈希表

目录

• 哈希表
• 哈希冲突（Hash Collision）
• JDK1.8的哈希冲突解决方案
• 哈希函数
• 如何生成key的哈希值
• Long和Double的哈希值
• 字符串的哈希值
• 关于31的探讨
• 自定义对象的哈希值
• 自定义对象作为key
• 哈希值的进一步处理:扰动计算
• 装填因子
• TreeMap vs HashMap
• LinkedHashMap
• 关于使用%来计算索引

一 哈希表

• 哈希表也叫做散列表（ hash 有剁碎的意思）

• 它是如何实现高效处理数据的？

  • put("Jack", 666);
  • put("Rose", 777);
  • put("Kate", 888);

image

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

• 添加、搜索、删除的流程都是类似的

1. 利用哈希函数生成 key 对应的 index【O(1)】
2. 根据 index 操作定位数组元素【O(1)】

• 哈希表是【空间换时间】的典型应用

• 哈希函数，也叫做散列函数

• 哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array

二 哈希冲突（Hash Collision）

• 哈希冲突也叫做哈希碰撞

1. 2 个不同的 key，经过哈希函数计算出相同的结果
2. key1 ≠ key2 ，hash(key1) = hash(key2)

image

• 解决哈希冲突的常见方法

1. 开放定址法（Open Addressing）
   ✓ 按照一定规则向其他地址探测，直到遇到空桶

2. 再哈希法（Re-Hashing）
   ✓ 设计多个哈希函数

3. 链地址法（Separate Chaining）
   ✓ 比如通过链表将同一index的元素串起来

三 JDK1.8的哈希冲突解决方案

image

• 默认使用单向链表将元素串起来

• 在添加元素时，可能会由单向链表转为红黑树来存储元素

  • 比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时

• 当红黑树节点数量少到一定程度时，又会转为单向链表

• JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突

• 思考：这里为什么使用单链表？

  • 每次都是从头节点开始遍历
  • 单向链表比双向链表少一个指针，可以节省内存空间

四 哈希函数

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

1. 先生成 key 的哈希值（必须是整数）
2. 再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值

- (int)hash:(Object key) {
    return hash_code(key) % table.length;
}

• 为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（2n）

- (int)hash:(Object key) {
    return hash_code(key) & (table.length - 1);
}

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

五 如何生成key的哈希值

key 的常见种类可能有

1. 整数、浮点数、字符串、自定义对象
2. 不同种类的 key，哈希值的生成方式不一样，但目标是一致的
   2.1 尽量让每个 key 的哈希值是唯一的
   2.2 尽量让 key 的所有信息参与运算
3. 在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null
4. 整数
   4.1 整数值当做哈希值
   4.2 比如 10 的哈希值就是 10

- (int)hashCode:(int value) {
    return value;
}

5. 浮点数
   5.1 将存储的二进制格式转为整数值

- (int)hashCode:(float value) {
    return floatToIntBits(value);
}

六 Long和Double的哈希值

• Long的哈希值

- (int)hashCode:(long value) {
    return (int)(value ^ (value >>> 32));
}

• Double的哈希值

- (int)hashCode:(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

>>> 和 ^ 的作用是？

• 高32bit 和 低32bit 混合计算出 32bit 的哈希值
• 充分利用所有信息计算出哈希值

image

七 字符串的哈希值

• 整数 5489 是如何计算出来的?

5 * 10^3 + 4∗10^2 + 8∗10^1 + 9∗10^0

• 字符串是由若干个字符组成的
  • 比如字符串 jack，由 j、a、c、k 四个字符组成(字符的本质就是一个整数)
  • 因此，jack的哈希值可以表示为 j∗n^3 + a∗n^2 + c∗n^1 + k∗n^0，等价于[(j∗n+a)∗n+c]∗n+k
  • 在JDK中，乘数 n 为 31，为什么使用 31?

31 是一个奇素数，JVM会将 31 * i 优化成(i << 5) – i

String string = "jack";
int hashCode = 0;
int len = string.length();
for (int i = 0; i < len; i++) {
    char c = string.charAt(i);
    hashCOde = 31 * hashCode + c;
}

String string = "jack";
int hashCode = 0;
int len = string.length();
for (int i = 0; i < len; i++) {
    char c = string.charAt(i);
    hashCOde = (hashCode << 5) - hashCode + c;
}

八 关于31的探讨

31 * i = (2^5 – 1) * i = i * 2^5 – i = (i << 5) – i

31不仅仅是符合2^n – 1，它是个奇素数(既是奇数，又是素数，也就是质数)

素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突

最终选择31是经过观测分布结果后的选择

九 自定义对象的哈希值

• Person.h

/** age */
@property(nonatomic,assign)int age;
/** height */
@property(nonatomic,assign)float height;
/** name */
@property(nonatomic,strong)NSString *name;

/// 初始化
- (instancetype)initWithAge:(int)age height:(float)height name:(NSString *)name;

/// 用来比较两个对象是否相对
- (BOOL)equals:(id)obj;

/// hash code
- (int)hasCode;

/// 年龄比较
- (int)compartTo:(Person *)per;

@end

• Person.m

@implementation Person

- (instancetype)initWithAge:(int)age height:(float)height name:(NSString *)name {
    self = [super init];
    if (self) {
        self.age = age;
        self.height = height;
        self.name = name;
    }
    return self;
}

/// 用来比较两个对象是否相对
- (BOOL)equals:(id)obj {
    // 内存地址
    if (obj == self) {
        return YES;
    }
    if (obj == nil || ![obj isKindOfClass:[Person class]]) {
        return NO;
    }
    // 比较成员变量
    Person *per = (Person *)obj;

    return per.age == self.age && per.height == self.height && per.name == self.name;
}

/// hash code
- (int)hasCode {
    NSUInteger hashCode = [NSString stringWithFormat:@"%d",self.age].hash;
    hashCode = hashCode * 31 + [NSString stringWithFormat:@"%f",self.height].hash;
    hashCode = hashCode * 31 + (self.name.length > 0 ? self.name.hash : 0);

    return (int)hashCode;
}

/// 年龄比较
- (int)compartTo:(Person *)per {
    return self.age - per.age;
}

@end

思考几个问题
1 哈希值太大，整型溢出怎么办? 不用作任何处理

十 自定义对象作为key

自定义对象作为 key，最好同时重写 hashCode 、equals 方法

1. equals :用以判断 2 个 key 是否为同一个 key

• 自反性 对于任何非null 的x，x.equals(x)必须返回true
• 对称性 对于任何非 null 的 x、y，如果 y.equals(x) 返回 true，x.equals(y) 必须返回 true
• 传递性 对于任何非 null 的 x、y、z，如果 x.equals(y)、y.equals(z) 返回 true，那么x.equals(z) 必须 返回 true
• 一致性 对于任何非 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 同时存在哈希表中

十一 哈希值的进一步处理:扰动计算

- (int)hash:(K key) {
    if (key == nil) {
        return 0;
    }

    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (self.table.length - 1);
}

十二 装填因子

装填因子(Load Factor) 节点总数量 / 哈希表桶数组长度，也叫做负载因子

在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍

十三 TreeMap vs HashMap

1. 何时选择TreeMap?

• 元素具备可比较性且要求升序遍历(按照元素从小到大)

2. 何时选择HashMap?

• 无序遍历

十四 LinkedHashMap

在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的

image

假设添加的顺序是

37，21，31，41，97，95，52，48，83

删除度为2的节点node时
需要注意更换 node 与 前驱\后继节点 的连接位置

LinkedHashMap – 删除注意点

删除度为2的节点node时(比如删除31)

需要注意更换 node 与 前驱\后继节点 的连接位置

image

14.2 LinkedHashMap – 更换节点的连接位置

image

十五 关于使用%来计算索引

如果使用%来计算索引

• 建议把哈希表的长度设计为素数(质数)
• 可以大大减小哈希冲突

10%8 = 2 
20%8 = 4 
30%8 = 6 
40%8 = 0 
50%8 = 2 
60%8 = 4 
70%8 = 6

10%7 = 3 
20%7 = 6 
30%7 = 2 
40%7 = 5 
50%7 = 1 
60%7 = 4 
70%7 = 0

下面表格列出了不同数据规模对应的最佳素数，特点如下

• 每个素数略小于前一个素数的2倍
• 每个素数尽可能接近2的幂(2n)

image

---

项目链接地址 - 15_HashMap

---

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/c137dad93d8d
来源：简书