9.1哈希表(散列)-Google上机题

1)看一个实际需求，google公司的一个上机题:
2)有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查找到该员工的所有信息.
3)要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

9.2哈希表的基本介绍：

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

9.3哈希表示意图：

哈希表示意图

其中：

Emp类就是一个一个的雇员，有姓名id等属性；
EmpLinkedList类就是绿色的框框就是一个一个的链表，其中有头指针（可以让头指针就是一个Emp类的对象，再让head.next指向第一个雇员，也可以直接让头指针就只像第一个雇员，代码里是用后面这种方式实现的），还有一些增删查改的方法，如增加（找到某个指针的next ==None 然后让这个指针指向这个对象）这个EmpLinkedList就只是一个一个的链表在之前的链表章节学完后就很好理解
HashTab类是整个蓝色的框，可以把它看成一个列表，列表里面有size个元素，首先先将列表里的每个元素初始化即每个都赋值EmpLinkedList对象（因为在add方法的时候可以直接去调用这个对象），然后封装一个hashfun方法，可以求得hashid，然后在add方法的时候直接调用第hashid个元素里的add方法然后把emp对象传进去即可。

9.4代码实现：

注：代码没有实现得很完整，包括增删查改的方法并不是很完整，外层调用也没写好，这都是一些套用的代码，这里就没写了

class Emp():
    def __init__(self,id,name):
        self.id = id
        self.name = name
        self.next = None
class EmpList():
    def __init__(self):
        self.head = None
    
    def add(self,emp):
        if self.head == None:
            self.head = emp
        else:
            self.temppointer = self.head
            while self.temppointer.next != None:
                self.temppointer = self.temppointer.next
            self.temppointer.next = emp

    def list(self):
        self.temppointer = self.head
        # print(self.temppointer.id,self.temppointer.name)
        # print(self.temppointer)
        # print(self.temppointer.next)
        # print(self.temppointer.next.id,self.temppointer.next.name)
        while self.temppointer != None:
            print(self.temppointer.id,self.temppointer.name)
            self.temppointer = self.temppointer.next
    
    def delete(self,id):
        self.temppointer = self.head
        if self.temppointer.id == id:
            self.head = self.temppointer.next
            return
        while self.temppointer.next.id != id:
            if self.temppointer.next == None:
                print("not found")
                break
            self.temppointer = self.temppointer.next
        self.temppointer.next = self.temppointer.next.next

            
class HashTab():
    def __init__(self,size):
        self.size = size
        self.hasharray = [EmpList() for i in range(self.size)]
        # self.hasharray = []
        # for i in range(self.size):
        #     emplist = EmpList()
        #     self.hasharray.append(emplist)


    def hashfun(self,id):
        self.id = id
        return(int(self.id) % self.size)

    def add(self,emp):
        self.emp = emp
        self.hashid = self.hashfun(self.emp.id)
        # print(self.hashid)
        self.hasharray[self.hashid].add(self.emp)
    
    def list(self):
        for i in range(self.size):
            print("第 "+str(i+1)+"个数组存的是")
            self.hasharray[i].list()
    
    def delete(self,id):
        self.hashid = self.hashfun(id)
        self.hasharray[self.hashid].delete(id)



hash = HashTab(7)
emp1 = Emp(1,'q')
emp2 = Emp(2,'q')
emp3 = Emp(3,'q')
emp4 = Emp(4,'q')
emp7 = Emp(7,'q')
emp8 = Emp(8,'q')
emp9 = Emp(9,'w')

hash.add(emp1)
hash.add(emp2)
hash.add(emp3)
hash.add(emp4)
hash.add(emp7)
hash.add(emp8)
hash.add(emp9)
hash.list()
hash.delete(8)
hash.delete(2)
hash.list()