哈希表简介

基本介绍

思路分析

代码实现

# 哈希表
# 员工信息
class Emp:
    id: int = 0
    name: str = ''
    next = None
 
    def __init__(self, id, name):
        self.id = id
        self.name = name
 
    def __str__(self):
        return f"id={self.id}, name={self.name}"
 
 
class EmpLinkedList:
    # 头指针，指向第一个 Emp，即链表的head指向的是第一个数据节点
    head: Emp = None
 
    # 添加员工到链表
    # 此处假设输入的员工ID是递增的
    def add(self, emp: Emp):
        if self.head is None:
            self.head = emp
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next  # 后移
        # 找到链表的最后位置，将新员工节点添加在链表最后
        cur.next = emp
 
    # 遍历链表
    def list(self):
        if self.head is None:
            print("当前链表为空")
            return
 
        cur = self.head
        while cur is not None:
            print(" => ", cur)
            cur = cur.next  # 后移，继续遍历
 
    # 根据id查找员工信息
    def find_emp_by_id(self, id: int):
        if self.head is None:
            print("当前链表为空")
            return
        cur = self.head
        while cur is not None:
            if cur.id == id:
                break  # 此时 cur 指向的节点就是要查找的员工
            cur = cur.next
 
        return cur
 
 
class HashTab:
    def __init__(self, size):
        self.size = size
        self.emp_linkedlist = [EmpLinkedList() for i in range(size)]
 
    def add(self, emp: Emp):
        # 根据员工ID，得到该员工应当添加到表里的哪条链表
        linked_list_no = self.hash_func(emp.id)
        self.emp_linkedlist[linked_list_no].add(emp)
 
    # 根据id查找员工信息
    def find_emp_by_id(self, id: int):
        linked_list_no = self.hash_func(id)
        emp = self.emp_linkedlist[linked_list_no].find_emp_by_id(id)
        if emp:
            print("员工信息为：", emp)
        else:
            print(f"没有找到id为{id}的员工")
 
    # 遍历所有链表，即遍历哈希表中的所有链表
    def list(self):
        for i in range(self.size):
            print(f"第{i + 1}条链表员工信息：", end="")
            self.emp_linkedlist[i].list()
 
    # 散列函数，此处用最简单的取模法实现
    def hash_func(self, id):
        return id % self.size
 
 
def hash_test():
    hash_tab = HashTab(7)
    while True:
        select = None
        print("1. 添加员工信息")
        print("2. 输出全部员工信息")
        print("3. 根据id查找员工")
        print("4. 退出")
 
        select = int(input("请选择："))
        if select == 1:
            id = int(input("请输入员工id："))
            name = input("请输入员工姓名：")
            emp = Emp(id, name)
            hash_tab.add(emp)
        elif select == 2:
            hash_tab.list()
        elif select == 3:
            id = int(input("请输入员工id："))
            hash_tab.find_emp_by_id(id)
        elif select == 4:
            break
        else:
            print("输入错误，没有该选项，请重新选择")
 
 
hash_test()