定义：
- 散列是一种用于以常数平均时间执行插入，删除和查找的技术。
- 我们将每个关键字被映射到从0到TableSize - 1这个范围中的某个数。这个映射称为散列函数。
- 散列函数需要保证任何两个不同的关键字映射到不同的单元。
- 当两个关键字散列到同一个值时(这叫做冲突), 应该做什么以及如何确定散列表的大小。
hash_table.png
散列函数：
- 一般简单合理的方法是直接返回Key mod TableSize， 并且保证表的大小为素数。
a. 假设关键字是字符串，一种选择办法是将字符串的ASCII码(或Unicode码)值加起来
public static int hash(String key, int tableSize){
int hashVal = 0;
for (int i = 0; i < key.length(); i ++){
hashVal += key.charAt(i);
}
return hashVal % tableSize;
}
这种方法实现起来简单合理，但如果表很大的话，并不会很好地分配关键字。例如，TableSize = 10007，假设所有的关键字至多8个字符长，由于ASCII码字符的值最多是127，那么它们的值是在0到1016之间，显然这不是一种均匀的分配。
*b. *假设关键字至少有三个字符，可以采用如下方法：
public static int hash(String key, int tableSize){
return (key.charAt(0) + key.charAt(1) * 27 + key.charAt(2) * 729) % tableSize;
}
但这样依旧不能完全均匀地分配，因为3个字母的不同组合数实际只有2851，也就是只有大约表的28%被真正散列到。
c. 根据Horner法则计算一个(37)的多项式函数：
Paste_Image.png
public static int hash(String key, int tableSize){
int hashVal = 0;
for (int i = 0; i < key.length(); i ++){
hashVal = 37 * hashVal + key.charAt(i);
}
hashVal %= tableSize;
//产生负数的情况
if (hashVal < 0){
hashVal += tableSize;
}
return hashVal;
}
解决冲突的两种方法：
- 分离链接法：将散列到同一个值的所有元素保留到一个表中。
- 开放定址法：尝试另外一些单元，直到找到空的单元为止。
*a. 分离链表法： *
separate_chaining.png
- 定义表的基本变量：
//定义默认表的大小
private static final int DEFAULT_TABLE_SIZE = 101;
//定义表的存储
private List<AnyType>[] theLists;
//定义表当前的大小
private int currentSize;
- 定义其构造函数，进行初始化：
public SeparateChainingHashTable(){
this(DEFAULT_TABLE_SIZE);
}
//进行初始化操作
public SeparateChainingHashTable(int size){
//初始化表，这里调用了一个nextPrime函数，以保证其表的大小为素数
theLists = new LinkedList[nextPrime(size)];
//初始化表中的链表
for (int i = 0; i < theLists.length; i ++){
theLists[i] = new LinkedList<AnyType>();
}
}
//返回下一个素数
private static int nextPrime(int n){
while (!isPrime(n)){
n ++;
}
return n;
}
//判断是否为素数
private static boolean isPrime(int n){
for (int i = 2; i <= Math.sqrt(n); i ++){
if (n % i == 0 && n != 2){
return false;
}
}
return true;
}
- 进行插入操作：如果这个元素是新元素，则它将被插入到链表的前端，因为往往新近插入的元素最有可能不久被访问。
public void insert(AnyType x){
//获取x根据hash后找到所对应的位置
List<AnyType> whichList = theLists[myHash(x)];
//如果当前位置链表不包含元素，则进行插入操作
if (!whichList.contains(x)){
//进行添加
whichList.add(x);
//判断是否达到表的长度，若达到则进行rehash操作，以扩大表的大小
if (++ currentSize > theLists.length){
rehash();
}
}
}
//根据值获取到其对应的hash位置
private int myHash(AnyType x){
int hashVal = x.hashCode();
hashVal %= theLists.length;
//考虑到负数的情况
if (hashVal < 0){
hashVal += theLists.length;
}
return hashVal;
}
private void rehash(){
//获取到原来的表
List<AnyType>[] oldLists = theLists;
//对现有的表大小进行扩大
theLists = new List[nextPrime(2 * theLists.length)];
//初始化新表
for (int j = 0; j < theLists.length; j ++){
theLists[j] = new LinkedList<AnyType>();
}
//初始化大小
currentSize = 0;
//将旧表中的数据重新插入到新表中
for (int i = 0; i < oldLists.length; i ++){
for (AnyType item : oldLists[i]){
insert(item);
}
}
}
- 删除操作：
//删除操作
public void remove(AnyType x){
//获取到对应位置的链表
List<AnyType> whichList = theLists[myHash(x)];
//检查是否包含元素，包含则进行删除操作，并大小--
if (whichList.contains(x)){
whichList.remove(x);
currentSize --;
}
}
- 检查元素：
//检查是否包含某个元素
public boolean contains(AnyType x){
List<AnyType> whichList = theLists[myHash(x)];
return whichList.contains(x);
}
- 打印链表：
//打印链表结构
public void printHashTable(){
for (int i = 0; i < theLists.length; i ++){
if (theLists[i] != null && theLists[i].size() > 0){
System.out.println("current position is : " + i );
for (AnyType x : theLists[i]){
System.out.println(x);
}
}
}
}
- 进行检测：为了效果更明显，我们强制表的结果为10，当然在实际项目中不可如此，这里只是为了测试作用。
public static void main(String[] args){
int[] arr = {0, 81,1, 64,4, 25,36,16,49,9};
SeparateChainingHashTable<Integer> separateChainingHashTable = new SeparateChainingHashTable<>(10);
//进行插入操作
for (int i = 0; i < arr.length; i ++){
separateChainingHashTable.insert(arr[i]);
}
//打印链表
separateChainingHashTable.printHashTable();
}
- 运行结果如下：
current position is : 0
0
current position is : 1
81
1
current position is : 4
64
4
current position is : 5
25
current position is : 6
36
16
current position is : 9
49
9
separate chaning.png
- 当然除了插入默认的基本类型，我们还可以插入对象，但一定要重定义对象的equals()和hashCode()方法
public class Employee {
private String name;
private double salary;
private int seniority;
//构造函数
public Employee(String name, double salary, int seniority){
this.name = name;
this.salary = salary;
this.seniority = seniority;
}
//判断对象是否相同
public boolean equals(Object rhs){
//满足为Employee类型且名字相同
return rhs instanceof Employee && name.equals(((Employee) rhs).name);
}
//重写hashCode
public int hashCode(){
return name.hashCode();
}
//打印对象
@Override
public String toString() {
return "name: " + name + " salary: " + salary + " seniority: " + seniority + "\n";
}
}
public static void main(String[] args){
SeparateChainingHashTable<Employee> hashTable = new SeparateChainingHashTable<>(11);
hashTable.insert(new Employee("worker", 1000,3));
hashTable.insert(new Employee("worker", 1500,3));
hashTable.insert(new Employee("worker", 1600,3));
hashTable.insert(new Employee("Manager", 2000, 2));
hashTable.insert(new Employee("Manager", 2500, 2));
hashTable.insert(new Employee("boss", 3000, 1));
hashTable.printHashTable();
}
结果如下：
current position is : 6
name: Manager salary: 2000.0 seniority: 2
current position is : 7
name: boss salary: 3000.0 seniority: 1
current position is : 10
name: worker salary: 1000.0 seniority: 3
我们可以看到对于name相同的对象是不会重复插入的。
完整代码：
public class SeparateChainingHashTable<AnyType> {
public SeparateChainingHashTable(){
this(DEFAULT_TABLE_SIZE);
}
//进行初始化操作
public SeparateChainingHashTable(int size){
//初始化表，这里调用了一个nextPrime函数，以保证其表的大小为素数
theLists = new LinkedList[nextPrime(size)];
//初始化表中的链表
for (int i = 0; i < theLists.length; i ++){
theLists[i] = new LinkedList<AnyType>();
}
}
public void insert(AnyType x){
//获取x根据hash后找到所对应的位置
List<AnyType> whichList = theLists[myHash(x)];
//如果当前位置链表不包含元素，则进行插入操作
if (!whichList.contains(x)){
//进行添加
whichList.add(x);
//判断是否达到表的长度，若达到则进行rehash操作，以扩大表的大小
if (++ currentSize > theLists.length){
rehash();
}
}
}
//删除操作
public void remove(AnyType x){
//获取到对应位置的链表
List<AnyType> whichList = theLists[myHash(x)];
//检查是否包含元素，包含则进行删除操作，并大小--
if (whichList.contains(x)){
whichList.remove(x);
currentSize --;
}
}
//检查是否包含某个元素
public boolean contains(AnyType x){
List<AnyType> whichList = theLists[myHash(x)];
return whichList.contains(x);
}
public void makeEmpty(){
for (int i = 0; i < theLists.length; i ++){
theLists[i].clear();
}
}
//定义默认表的大小
private static final int DEFAULT_TABLE_SIZE = 101;
//定义表的存储
private List<AnyType>[] theLists;
//定义表当前的大小
private int currentSize;
//根据值获取到其对应的hash位置
private int myHash(AnyType x){
int hashVal = x.hashCode();
hashVal %= theLists.length;
//考虑到负数的情况
if (hashVal < 0){
hashVal += theLists.length;
}
return hashVal;
}
private void rehash(){
//获取到原来的表
List<AnyType>[] oldLists = theLists;
//对现有的表大小进行扩大
theLists = new List[nextPrime(2 * theLists.length)];
//初始化新表
for (int j = 0; j < theLists.length; j ++){
theLists[j] = new LinkedList<AnyType>();
}
//初始化大小
currentSize = 0;
//将旧表中的数据重新插入到新表中
for (int i = 0; i < oldLists.length; i ++){
for (AnyType item : oldLists[i]){
insert(item);
}
}
}
//返回下一个素数
private static int nextPrime(int n){
while (!isPrime(n)){
n ++;
}
return n;
}
//判断是否为素数
private static boolean isPrime(int n){
for (int i = 2; i <= Math.sqrt(n); i ++){
if (n % i == 0 && n != 2){
return false;
}
}
return true;
}
//打印链表结构
public void printHashTable(){
for (int i = 0; i < theLists.length; i ++){
if (theLists[i] != null && theLists[i].size() > 0){
System.out.println("current position is : " + i );
for (AnyType x : theLists[i]){
System.out.println(x);
}
}
}
}
}
