一文详解Python中哈希表的使用

'''
哈希函数
'''
def hash_code(key):
    # 设置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 4

# 哈希表
hash_table = [None] * 4
# 计算关键字的哈希值
idx = hash_code('zjl')
# 根据关键字换算出来的位置存储数据
hash_table[idx] = '周杰伦'
idx = hash_code('llj')
hash_table[idx] = '李连杰'
idx = hash_code('cl')
hash_table[idx] = '成龙'
idx = hash_code('zzz')
hash_table[idx] = '张志忠'
print('哈希表中的数据：', hash_table)
'''
输出结果：
哈希表中的数据： ['周杰伦', None, '张志忠', '成龙']
'''

'''
哈希函数
'''
def hash_code(key):
    # 设置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 8

# 哈希表
hash_table = [None] * 8

# 保存所有学生
idx = hash_code('zjl')
hash_table[idx] = '周杰伦'
idx = hash_code('llj')
hash_table[idx] = '李连杰'
idx = hash_code('cl')
hash_table[idx] = '成龙'
idx = hash_code('zzz')
hash_table[idx] = '张志忠'
print('哈希表中的数据：', hash_table)
'''
输出结果：
哈希表中的数据： ['周杰伦', None, '李连杰', None, None, None, '张志忠', '成龙']
'''

'''
移位叠加哈希算法
'''
def hash_code(key, hash_table_size):
    # 转换成字符串
    key_s = str(key)
    # 保存求和结果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        s += int(key_s[i:i + 3])
    return s % hash_table_size

# 商品信息
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表长度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式进行存储
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 显示哈希表中的数据
print("哈希表中的数据：",hash_table)
# 根据订单号进行查询
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("订单号为{0}的金额为{1}".format(19981112, val))
'''
输出结果
哈希表中的数据： [None, None, 300, 400.0, None, None, 200, None, None, None]
订单号为19981112的金额为300
'''

'''
间界叠加哈希算法
'''
def hash_code(key, hash_table_size):
    # 转换成字符串
    key_s = str(key)
    # 保存求和结果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        # 切片
        tmp_s = key_s[i:i + 3]
        # 反转
        if i % 2 != 0:
            tmp_s = tmp_s[::-1]
        s += int(tmp_s)
    return s % hash_table_size

# 商品信息（数据样例）
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表长度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式进行存储
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 显示哈希表中的数据
print("哈希表中的数据：", hash_table)
# 根据订单号进行查询
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("订单号为{0}的金额为{1}".format(19981112, val))
'''
输出结果：
哈希表中的数据： [None, None, None, 400.0, None, None, 200, None, None, 300]
订单号为19981112的金额为300
'''

'''
哈希算法
平方取中
'''
def hash_code(key, hash_table_size):
    # 求平方
    res = key ** 2
    #  取中间值，这里取中间 2 位（简化问题）
    res = int(str(res)[1:3])
    # 取余数
    return res % hash_table_size

hash_table_size = 10
hash_table = [None]*hash_table_size
# 图书信息
books = [[58, "python 从入门到精通"], [67, "C++ STL"], [78, "Java 内存模型"]]
for b in books:
    hash_val = hash_code(b[0],hash_table_size)
    hash_table[hash_val]=b[1]

# 显示哈希表中的数据
print("哈希表中的数据：", hash_table)
# 根据编号进行查询
hash_val = hash_code(67, hash_table_size)
val = hash_table[hash_val]
print("编号为{0}的书名为{1}".format(67, val))

'''
线性探测法解决哈希冲突
'''
def hash_code(key, hash_table, num):
    # 哈希表的长度
    size = len(hash_table)
    # 取余数法计算哈希值
    hash_val = key % num
    # 检查此位置是否已经保存其它数据
    if hash_table[hash_val] is not None:
        # 则从hash_val 之后寻找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] is None:
                hash_val = i
                break
    return hash_val

# 哈希表
hash_table = [None] * 15
src_nums = [25, 78, 56, 32, 88, 26, 73, 81, 14]
for n in src_nums:
    hash_val = hash_code(n, hash_table, 13)
    hash_table[hash_val] = n

print("哈希表中的数据：", hash_table)
'''
输出结果：
哈希表中的数据： [78, 26, 14, 81, 56, None, 32, None, 73, None, 88, None, 25, None, None]
'''

for i in range(hash_val + 1, size + hash_val):
	 pass

def get(key, hash_table, num):
    # 哈希表的长度
    size = len(hash_table)
    # 取余数法计算哈希值
    hash_val = key % num
    is_exist = False
    # 检查此位置是否已经保存其它数据
    if hash_table[hash_val] is None:
        # 不存在
        return None
    if hash_table[hash_val] != key:
        # 则从hash_val 之后寻找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] == key:
                hash_val = i
                is_exist = True
                break
    else:
        is_exist=True
    if is_exist:
        return hash_val

# 测试   
res = get(25, hash_table, 13)
print(res)

'''
结点类
'''
class HashNode():
    def __init__(self, value):
        self.value = value
        self.next_node = None

'''
哈希类
'''
class HashTable():
    def __init__(self):
        # 哈希表,初始大小为 15，可以根据需要动态修改
        self.table = [None] * 15
        # 实际数据大小
        self.size = 0

    '''
    存储数据
    key:关键字
    value:值
    '''

    def put(self, key, value):
        hash_val = self.hash_code(key)
        # 新结点
        new_node = HashNode(value)
        if self.table[hash_val] is None:
            # 本代码采用首结点保存数据方案
            self.table[hash_val] = new_node
            self.size+=1
        else:
            move = self.table[hash_val]
            while move.next_node is not None:
                move = move.next_node
            move.next_node = new_node
            self.size+=1

    '''
    查询数据
    '''
    def get(self, key):
        hash_val = self.hash_code(key)
        if self.table[hash_val] is None:
            # 数据不存在
            return -1

        if self.table[hash_val].value == key:
            # 首结点就是要找的数据
            return self.table[hash_val].value

        # 移动指针
        move = self.table[hash_val].next_node
        while move.value != key and move is not None:
            move = move.next_node
        if move is None:
            return -1
        else:
            return move.value

    def hash_code(self, key):
        # 这里仅为说明问题，13 的选择是固定的
        hash_val = key % 13
        return hash_val


# 原始数据
src_nums = [25, 78, 56, 32, 88, 26, 39, 82, 14]
# 哈希对象
hash_table = HashTable()
# 把数据添加到哈希表中
for n in src_nums:
    hash_table.put(n, n)
# 输出哈希表中的首结点数据
for i in hash_table.table:
    if i is not None:
        print(i.value,end=" ")
print("\n-------------查询-----------")
print(hash_table.get(26))
'''
输出结果：
78 14 56 32 88 25 
-------------查询-----------
26
'''