散列 hasing
1. 散列 hashing
定义
散列，又称哈希（Hash），是把任意长度的输入（又叫映射），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射。
数组本身就是散列表（hash table）。
理想的散列
如果数组hashTable有10000个元素，则每个元素都对应于或映射到hashTable中唯一的一个元素，该元素引用相应的对象，则这是理想散列。
完美的散列函数将每个查找键映射为不同整数，以该整数作为散列表的索引正合适。
典型的散列
但是绝大多数的散列表却不满，甚至是稀疏的，即仅有少量元素被实际用到。对于数组10000个元素如果一对一映射，则浪费了分配给这个散列表绝大部分的空间，如果只有700个元素且不是连续的，则需要一个更小的散列表。
给定一个非负整数i与一个含有n个位置的散列表，i对n取模的值得范围从0到n-1。即i对n的模就是i除以n的整数余，则这个值就是散列表的合法索引。
散列算法
1. 将查找键转换为一个称为散列码（hash code）的整数
2. 将散列压缩（compress）到散列表的索引范围
查找键往往不是整数，而是字符串。因此，散列函数首先要将查找键转换为一个整数散列码，然后将这个整数转换为一个作为特定的散列表的索引。
冲突
由于10000个元素映射到tableSize个索引，则某些元素被映射到相同的索引，这一现象称为冲突。
典型的散列函数不是完美的，因为他们可以允许不止一个查找键映射到同一个索引，导致散列表的冲突。
2. 散列码
为了减少冲突的几率，应选择/使元素均匀分布在散列表中的散列函数。
类类型的散列码
Java的基类Object有一个方法hashCode返回一个整数散列码。这个默认的散列码通常不适合用于散列，因为他对于两个相等的对象将有不同的散列码。为了对词典之类的实现有用，散列码必须将相等的对象映射到散列表中的相同位置。
即：
如果一个类覆盖了equals方法，则应该覆盖hashCode方法；
如果equals方法认为这个对象相等，则hashCode对这两个对象必须返回相同的值；
如果在程序执行过程中，一个对象不止一次调用hashCode，并且如果在这段时间内对象的数据保持不变，则hashCode必须返回相同的散列码；
在同一个程序的两次执行过程中，对象的散列码可以不同。
This chapter requires login to view full content. You are viewing a preview.
Login to View Full ContentCourse Curriculum
编程根基：数据结构、算法与系统基础
Java 内核：JVM 与并发编程
框架与 I/O：Spring、Netty 与 Web 容器
高性能中间件：消息、缓存与存储
架构能力：高可用、DDD 与系统设计
云原生：容器化、可观测性与工程效能
Speaker
