08 哈希表

哈希表详解

1. 引言

哈希表（Hash Table）是一种常用于快速查找的数据结构，它通过哈希函数将键映射到数组的特定位置，以实现快速的插入、删除和查找操作。

2. 哈希表原理

哈希表的原理基于哈希函数，这是一种能够将任意大小的数据映射到固定大小范围的函数。哈希表由一个数组和一个哈希函数组成。当插入一个键值对时，哈希函数计算键的哈希值，然后将该值映射到数组的特定位置。在查找时，哈希表再次使用哈希函数找到键的位置，从而实现快速的查找。

3. 解决冲突的方法

由于哈希函数的映射并非唯一，可能出现多个键映射到同一个位置的情况，称为冲突。解决冲突的常见方法有：

3.1 链地址法

每个哈希表位置维护一个链表，所有映射到该位置的键值对都存储在链表中。

3.2 开放地址法

当冲突发生时，通过线性探测、二次探测等方法在哈希表中寻找下一个可用位置。

4. 哈希表的应用场景

哈希表广泛应用于各种场景，包括：

• 数据库索引：加速数据库中记录的查找。
• 缓存实现：存储最近访问的数据，提高访问速度。
• 字典数据结构：实现键值对的快速插入、删除和查找。

5. 哈希表的代码示例

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            self.table[index].append((key, value))

    def search(self, key):
        index = self._hash(key)
        if self.table[index] is not None:
            for k, v in self.table[index]:
                if k == key:
                    return v
        return None

    def delete(self, key):
        index = self._hash(key)
        if self.table[index] is not None:
            for i, (k, v) in enumerate(self.table[index]):
                if k == key:
                    del self.table[index][i]
                    return

package org.example;  
  
import java.util.Scanner;  
  
public class HashTableDemo {  
    public static void main(String[] args) {  
        //创建一个哈希表  
        HashTable hashTable = new HashTable(7);  
        //写一个简单菜单  
        String key = "";  
        Scanner scanner = new Scanner(System.in);  
  
        while (true) {  
            System.out.println("add：添加雇员");  
            System.out.println("list：显示雇员");  
            System.out.println("find：查找雇员");  
            System.out.println("exit：退出系统");  
            key = scanner.next();  
  
            switch (key) {  
                case "add":  
                    System.out.println("输入id");  
                    int id = scanner.nextInt();  
                    System.out.println("输入名字");  
                    String name = scanner.next();  
                    Emp emp = new Emp(id, name);  
                    hashTable.add(emp);  
                    break;  
                case "list":  
                    hashTable.list();  
                    break;  
                case "find":  
                    System.out.println("输入要查找的id");  
                    id = scanner.nextInt();  
                    hashTable.findEmpById(id);  
                    break;  
                case "exit":  
                    scanner.close();  
                    System.exit(0);  
                default:  
                    break;  
            }  
        }  
    }  
}  
  
//创建哈希表，用于管理多条链表  
class HashTable {  
    private EmpLinkedList[] empLinkedListArray;  
    private int size;//链表条数  
  
    public HashTable(int size) {  
        this.size = size;  
        // 初始化empLinkedListArray  
        empLinkedListArray = new EmpLinkedList[size];  
        //能不能直接用，不要忘了分别初始化每个链表  
        for (int i = 0; i < size; i++) {  
            empLinkedListArray[i] = new EmpLinkedList();  
        }  
    }  
  
    public void add(Emp emp) {  
        //根据员工id得到该员工应当加入到哪条链表  
        int empLinkedListNO = hashFun(emp.id);  
        //emp添加到对应的链表中  
        empLinkedListArray[empLinkedListNO].add(emp);  
    }  
  
    public void list() {  
        for (int i = 0; i < size; i++) {  
            empLinkedListArray[i].list(i);  
        }  
    }  
  
    //编写散列函数，使用取模法  
    public int hashFun(int id) {  
        return id % size;  
    }  
  
    //根据输入的id查找雇员  
    public void findEmpById(int id) {  
        int empLinkedListNO = hashFun(id);  
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);  
        if (emp != null) {  
            System.out.printf("在第%d条链表中找到 雇员id = %d\n", empLinkedListNO + 1, id);  
        } else {  
            System.out.println("在表中未找到");  
        }  
    }  
}  
  
class Emp {  
    public int id;  
    public String name;  
    public Emp next;  
  
    public Emp(int id, String name) {  
        super();  
        this.id = id;  
        this.name = name;  
    }  
  
  
}  
  
class EmpLinkedList {  
    //表示一条链表、一条数据  
    //头指针 指向第一个emp，因此head有效，直接指向第一个雇员  
    private Emp head;  
  
    //添加员工到链表  
    public void add(Emp emp) {  
        //假定添加雇员时，id自增长  
        //因此将该雇员加入本链表的最后即可  
        if (head == null) {  
            head = emp;  
            return;  
        }  
        //如果不是第一个，定义辅助指针帮助定位到最后  
        Emp curEmp = head;  
        while (true) {  
            if (curEmp.next == null) {  
                break;  
            }  
            curEmp = curEmp.next;  
        }  
        curEmp.next = emp;  
    }  
  
    //    遍历雇员信息  
    public void list(int no) {  
        if (head == null) {  
            System.out.println("第" + (no + 1) + "链表信息为空");  
            return;  
        }  
        System.out.print("第" + (no + 1) + "链表信息为：");  
        Emp curEmp = head;  
        while (true) {  
            System.out.printf("=> id=%d name=%s\t", curEmp.id, curEmp.name);  
            if (curEmp.next == null) {  
                //说明是最后节点  
                break;  
            }  
            curEmp = curEmp.next;  
        }  
        System.out.println();  
    }  
  
    //根据id查找雇员  
    //找到返回emp，找不到返回空  
    public Emp findEmpById(int id) {  
        //判断链表是否为空  
        if (head == null) {  
            System.out.println("链表为空");  
            return null;  
        }  
        Emp curEmp = head;  
        while (true) {  
            if (curEmp.id == id) {  
                break;//找dao  
            }  
            if (curEmp.next == null) {  
                //遍历结束仍未找到  
                curEmp = null;  
                break;  
            }  
            curEmp = curEmp.next;  
        }  
        return curEmp;  
    }  
}

6. 总结

在选择哈希函数时，需要考虑均匀性和碰撞的处理方法，以确保哈希表的高效性。