Udemy——Python数据结构与算法（9）

  课程：【Udemy高分付费课程】Python数据结构与算法 - 终极 Python 编码面试和计算机科学训练营（中英文字幕）_哔哩哔哩_bilibili

哈希表HashTable

通过将键（Key）映射到表中一个位置来访问记录，以加快查找速度。简单来说，它就像一个“字典”，你可以通过一个“索引”（键）快速找到对应的内容（值）。

基础代码

class HashTable:
    def __init__(self,size=7):
        self.data_map=[None]*size
    def __hash(self,key):
        my_hash=0
        for letter in key:
            my_hash=(my_hash+ord(letter)*23)%len(self.data_map)
        return my_hash
    def print_table(self):
        for i,val in enumerate(self.data_map):
            print(i,":",val)

添加设置   set_item

set_item(self,key,value):
        index=self.__hash(key)
        if self.data_map[index]==None:
            self.data_map[index]=[]
        self.data_map[index].append([key,value])


my_hash_table=HashTable()

my_hash_table.set_item("bolts",1400)
my_hash_table.set_item("washers",50)
my_hash_table.set_item("lumber",70)

my_hash_table.print_table()

效果

查找 get_item

    def get_item(self,key):
        index=self.__hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0]==key:    #第index索引里的第i个键值对的第0位 是否等于 在搜索的key
                    return self.data_map[index][i][1]  #返回第index索引里的第i个键值对的第1位 也就是数值value
        return None






my_hash_table=HashTable()

my_hash_table.set_item("bolts",1400)
my_hash_table.set_item("washers",50)

print(my_hash_table.get_item("bolts"))
print(my_hash_table.get_item("washers"))
print(my_hash_table.get_item("lumber"))

查询键 keys

    def keys(self):
        all_keys=[]
        for i in range(len(self.data_map)):
            if self.data_map[i] is not None:
                for j in range(len(self.data_map[i])):
                    all_keys.append(self.data_map[i][j][0])
        return all_keys


my_hash_table=HashTable()

my_hash_table.set_item("bolts",1400)
my_hash_table.set_item("washers",50)
my_hash_table.set_item("lumber",70)

print(my_hash_table.keys())

完整代码

class HashTable:
    def __init__(self,size=7):
        self.data_map=[None]*size
    def __hash(self,key):
        my_hash=0
        for letter in key:
            my_hash=(my_hash+ord(letter)*23)%len(self.data_map)
        return my_hash
    def print_table(self):
        for i,val in enumerate(self.data_map):
            print(i,":",val)
    def set_item(self,key,value):
        index=self.__hash(key)
        if self.data_map[index]==None:
            self.data_map[index]=[]
        self.data_map[index].append([key,value])
    def get_item(self,key):
        index=self.__hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0]==key:    #第index索引里的第i个键值对的第0位 是否等于 在搜索的key
                    return self.data_map[index][i][1]  #返回第index索引里的第i个键值对的第1位 也就是数值value
        return None
    def keys(self):
        all_keys=[]
        for i in range(len(self.data_map)):
            if self.data_map[i] is not None:
                for j in range(len(self.data_map[i])):
                    all_keys.append(self.data_map[i][j][0])
        return all_keys


my_hash_table=HashTable()

my_hash_table.set_item("bolts",1400)
my_hash_table.set_item("washers",50)
my_hash_table.set_item("lumber",70)

print(my_hash_table.keys())
#my_hash_table.print_table()