# 数据结构与算法–散列表

``````private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}``````

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

## 基于拉链法的散列表

``````package Chap8;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class SeparateChainingHashST<Key, Value> {

private int M; // 散列表的大小
private int N; // 键值对的个数
private SequentialST<Key, Value>[] st; // 存放链表的数组

public SeparateChainingHashST(int M) {
this.M = M;
st = (SequentialST<Key, Value>[]) new SequentialST[M];
// 每个索引都有一条链表
for (int i = 0; i < st.length; i++) {
st[i] = new SequentialST<>();
}
}

public SeparateChainingHashST() {
this(31);
}

private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}

public void put(Key key, Value value) {
if (N >= M / 2) {
resize(2 * M);
}
st[hash(key)].put(key, value);
N++;
}

public Value get(Key key) {
return st[hash(key)].get(key);
}

public Value delete(Key key) {
Value value = st[hash(key)].delete(key);
N--;
if (N > 0 && N <= M / 8) {
resize(M / 2);
}
return value;
}
// 每条链表中的键都加到一个集合中
public Set<Key> keys() {
Set<Key> keys = new HashSet<>();
for (int i = 0; i < M; i++) {
}
return keys;
}

public boolean isEmpty() {
return N == 0;
}

public boolean contains(Key key) {
return st[hash(key)].contains(key);
}

public int size() {
return N;
}

private void resize(int max) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<>(max);
// 所有键值对重新插入，可保证每个索引的链表长度保持在一个小的常数范围内
for (Key key : keys()) {
temp.put(key, get(key));
}
// 更新散列表的大小
M = temp.M;
// 更新散列表
st = temp.st;
}

@Override
public String toString() {
Iterator<Key> keys = keys().iterator();
if (isEmpty()) {
return "{}";
}
StringBuilder sb = new StringBuilder();
sb.append("{");
while (true) {
Key key = keys.next();
sb.append(key).append("=").append(get(key));
if (!keys.hasNext()) {
return sb.append("}").toString();
} else {
sb.append(", ");
}
}

}

public static void main(String[] args) {
SeparateChainingHashST<String, Integer> a = new SeparateChainingHashST<>();
a.put("a", 1);
a.put("b", 2);
a.put("c", 3);
a.put("d", 4);

a.delete("c");
System.out.println(a.keys());
System.out.println(a.size());
System.out.println(a);
}
}
``````

## 基于线性探测法的散列表

``````package Chap8;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class LinearProbingHashST<Key, Value> {
private int N; // 键值对的个数
private int M; // 散列表的大小
private Key[] keys;
private Value[] values;

public LinearProbingHashST(int cap) {
M = cap;
keys = (Key[]) new Object[cap];
values = (Value[]) new Object[cap];
}

public LinearProbingHashST() {
this(31);
}

private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}

public void put(Key key, Value value) {
if (N >= M / 2) {
resize(2 * M);
}
int i;
// 碰撞冲突，看下一个位置，如果这个过程中发现键已经存在，则更新并直接返回
for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
values[i] = value;
return;
}
}
// 若干位置后的第一个空位，插入新键值对
keys[i] = key;
values[i] = value;
N++;
}

public Value get(Key key) {
// 碰撞冲突，看下一个位置，如果这个过程中发现键已经存在，则更新并直接返回
for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
return values[i];
}
}
return null;
}

public Value delete(Key key) {
Value value = null;
int i = hash(key);

while (keys[i] != null) {
if (keys[i].equals(key)) {
value = values[i];
break;
}
i = (i + 1) % M;
}
// 找到键了，删除键值对
keys[i] = null;
values[i] = null;
// 删除后，这条键簇中，i之后的键值对都需要重新插入
// 因为get方法终止循环的条件是keys[i] != null，删除后键簇中那个位置是空位，之后的键都访问不到了
i = (i + 1) % M; // i之后的第一个位置
// 对这条键簇i之后的进行重新插入
while (keys[i] != null) {
Key keyRedo = keys[i];
Value valueRedo = values[i];
// 删了再插入
keys[i] = null;
values[i] = null;
N--;
put(keyRedo, valueRedo);

i = (i + 1) % M;
}

N--;
if (N > 0 && N <= M / 8) {
resize(M / 2);
}
return value;
}

private void resize(int max) {
LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(max);
// 所有键值对重新插入，可保证每个索引的链表长度保持在一个小的常数范围内
for (int i = 0; i < M; i++) {
if (keys[i] != null) {
temp.put(keys[i], values[i]);
}
}
// 更新散列表的大小
M = temp.M;
// 更新散列表的键和值
keys = temp.keys;
values = temp.values;
}

public Set<Key> keys() {
Set<Key> keySet = new HashSet<>();
for (int i = 0; i < M; i++) {
if (keys[i] != null) {
}
}
return keySet;
}

public boolean isEmpty() {
return N == 0;
}

public int size() {
return N;
}

public boolean contains(Key key) {
return get(key) != null;
}

@Override
public String toString() {
Iterator<Key> keys = keys().iterator();
if (isEmpty()) {
return "{}";
}
StringBuilder sb = new StringBuilder();
sb.append("{");
while (true) {
Key key = keys.next();
sb.append(key).append("=").append(get(key));
if (!keys.hasNext()) {
return sb.append("}").toString();
} else {
sb.append(", ");
}
}

}

public static void main(String[] args) {
LinearProbingHashST<String, Integer> a = new LinearProbingHashST<>();
a.put("a", 1);
a.put("b", 2);
a.put("c", 3);
a.put("d", 4);

a.delete("c");
System.out.println(a.keys());
System.out.println(a.size());
System.out.println(a);
}
}
``````

### 键簇

by @sunhaiyu

2017.10.23

原文作者：sunhaiyu
原文地址: https://www.cnblogs.com/sun-haiyu/p/7718100.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。