散列表

什么是 散列表?

 散列表(Hash Table,即哈希表)是根据键值(Key)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

为什么要有 散列表?

可以提供快速的插入操作和查找操作

 不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即 O(1) 的时间级
 实际上,这只需要几条机器指令
 哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器),而树的操作通常需要 O(N) 的时间级

编程实现相对容易

散列表工作机制

存储

 使用一个数组实现的无序符号表
 意味着, 数组创建后,难于扩展(某些哈希表被基本填满时,性能下降得非常严重)
 要么预设足够的空间,要么定期将数据迁移到更大的哈希表

查找

 首先,用散列函数将被查找的键转化为数组的一个索引
 其次,处理碰撞冲突

  • 拉链法
    使用原始的链表数据类型来扩展 SequentialSerchT
    为 M 个元素分别构建符号表来保存散列到这里的键
  • 线性探测法
    用大小为 M 的数组保存 N 个键值对(M > N, 依靠数组中空位解决碰撞冲突,此策略的所有方法统称为开放地址散列表)

散列表在 Java 中的相关实现:HashMap

java.lang.Object 的规范

  • 如果一个对象的 equals 方法做比较所用到的信息没有被修改的话,那么,对该对象调用 hashCode 方法多次,必须始终如一地返回同一个整数
  • 如果两个对象根据 equals(Object) 方法是相等,那么调用这两个对象中任意一个对象的 hashCode 方法必须产生同样的整数结果
  • 对于不相等的对象产生截然不同的整数结果, 有可能提高散列表的性能

HashMap 失效的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package com.yuzhouwan.hashCode2;

import java.util.HashMap;
import java.util.Map;

public final class PhoneNumber {
private final short areaCode;
private final short exchange;
private final short extension;

public PhoneNumber(int areaCode, int exchange, int extension) {
rangeCheck(areaCode, 999, "area code");
rangeCheck(exchange, 999, "exchange");
rangeCheck(extension, 9999, "extension");
this.areaCode = (short) areaCode;
this.exchange = (short) exchange;
this.extension = (short) extension;
}

private static void rangeCheck(int arg, int max, String name) {
if (arg < 0 || arg > max)
throw new IllegalArgumentException(name + ": " + arg);
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + areaCode;
result = prime * result + exchange;
result = prime * result + extension;
return result;
}

/**
* If u put the param that is not Object and forget use the annotation that name is 'Override',
* the equals method loses efficacy and u will find the reason hardly.
*/
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof PhoneNumber)) return false;
PhoneNumber pn = (PhoneNumber) o;
return pn.extension == extension &&
pn.exchange == exchange &&
pn.areaCode == areaCode;
}

public boolean equals2(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
PhoneNumber other = (PhoneNumber) obj;
if (areaCode != other.areaCode) return false;
if (exchange != other.exchange) return false;
if (extension != other.extension) return false;
return true;
}

/**
* if u do not rewrite the hashCode method,
* u will get the different hashCode when u init the same object, then the hashMap will work unusually.
*/
public static void main(String... args) {
Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();

PhoneNumber pn = new PhoneNumber(408, 867, 5309);
m.put(pn, "Jenny");

System.out.println("pn\' hashCode: " + pn.hashCode() + " - "
+ m.get(pn));

pn = new PhoneNumber(408, 867, 5309);
System.out.println("pn\' hashCode: " + pn.hashCode() + " - "
+ m.get(pn));
}
}

 如果没有 hashCode 的结果:

1
2
pn hashCode: 909751202 - Jenny
pn hashCode: 104885374 - null

处方

 1. 把某个非零长数值,比如说 17,保存在一个叫 result 的 int 类型变量中
 2. 对于对象中每一个关键域 f(指 equals 方法中考虑的每个域),完成以下步骤:
   a. 为该域计算 int 类型的散列码 c:

1
2
3
4
5
6
7
8
9
10
i. 如果该域是 boolean 类型,则计算 (f?0:1) 
ii. 如果该域是 bytecharshort 或者 int 类型,则计算 (int) f
iii. 如果该域是 long 类型,则计算 (int) (f ^ (f >>> 32))
iv. 如果该域是 float 类型,则计算 Float.floatToIntBits(f)
v. 如果该域是 double 类型,则计算 Double.doubleToLongBits(f) 得到一个 long 类型的值,然后按照步骤 2.a.iii,对该 long 型值计算散列值
vi. 如果该域是一个对象引用,并且该类的 equals 方法通过递归调用 equals 的方式来比较这个域,则同样对这个域递归调用 hashCode
 如果要求一个更为复杂的比较,则为这个域计算一个 "规范表示(canonical representation)",然后针对这个范式表示调用 hashCode
 如果这个域的值为 null,则返回 0(也可以设置为其他某个常数,但习惯上使用 0
vii. 如果该域是一个数组,则把每一个元素当做单独的域来处理
 也就是说,递归地应用上述规则,对每个重要的元素计算一个散列码,然后根据步骤 2.b 中的做法把这些散列值组合起来

  b. 按照下面的公式,把步骤 a 中计算得到的散列码 c 组合到 result 中:

1
result = 37 * result + c;

 3. 返回 result
 4. 写完了 hashCode 方法之后,问自己 “是否相等的实例具有相等的散列码”。如果不是的话,找出原因,并修改错误

冗余域(redundant field)

 如果一个域的值可以根据参与计算的其他域值计算出来,则把这样的域排除在外是可以接受的

ConcurrentHashMap 如何实现线程安全

 ConcurrentHashMap 中加了 lock 的方法(scanAndLockForPut、scanAndLock、lock 用来添加锁,并使用 try-finally 释放锁,以及使用 sun.misc.Unsafe 提供 volatile 变量

1
2
3
4
5
6
7
8
9
10
11
12
13
+ java.util.concurrent.ConcurrentHashMap.Segment<K, V>
- scanAndLockForPut + unclock
put
- scanAndLock + unclock
remove、replace
- lock + unclock
clear
- java.util.concurrent.locks.ReentrantLock.lock() + unlock()
size、containsValue

+ java.util.concurrent.locks.ReentrantLock.lock() -> java.util.concurrent.locks.ReentrantLock.Sync.lock()
+ java.util.concurrent.locks.ReentrantLock.unlock() -> java.util.concurrent.locks.AbstractQueuedSynchronizer.release(int)
writeObject(Serialization Support)

sun.misc.Unsafe.getObjectVolatile(Object, long)

1
2
get            // manually integrate access methods to reduce overhead
containsKey // same as get() except no need for volatile value read

readObject 中读取流中所有的 Object

1
2
3
4
5
6
7
8
// Read the keys and values, and put the mappings in the table
for (;;) { // = while(true)
K key = (K) s.readObject(); //java.io.ObjectInputStream
V value = (V) s.readObject();
if (key == null)
break; //只有达到这个条件, 才可以退出这个死循环
put(key, value);
}

欢迎加入我们的技术群,一起交流学习

人工智能 (高级)& (进阶)| BigData | 算法

Benedict Jin wechat
Subscribe to my blog by scanning my public wechat account.