哈希映射是一种将key与value关联起来的数据结构。通过将key通过哈希函数转化为一个数字,将这个数字与一个数组下标相关联,就可以实现将key与value进行快速查找。在Python中,Dictionary与Set就是哈希映射的两种实现方式。
一、Dictionary的使用
Dictionary,也叫做字典,是Python中内置的数据类型之一。可以将Dictionary看作是一种无序的键值对集合。其中每个键(key)都是唯一的,对应的值(value)可以是任意类型。下面是一个简单的例子:
{
"name": "Tom",
"age": 25,
"gender": "male"
}
在Python中,可以使用“{}”或者“dict()”来创建Dictionary,并且可以通过索引方式获取对应的值:
# 创建Dictionary
student = {
"name": "Tom",
"age": 25,
"gender": "male"
}
# 读取Dictionary
print(student["name"]) # Tom
print(student.get("age", 0)) # 25
Dictionary的特点之一是可以通过键来快速检查值是否存在:
if "name" in student:
print("Name is in the student dictionary.")
二、Set的使用
Set是另一种基于哈希表实现的数据结构。Set中存储的是一组互不相同的元素,类似于Dictionary中的key,可看作是一组不重复的值。Set中元素的排列顺序是无序的。
Set最常用的方式是将一个列表或者元组转化为一个Set,也可以直接使用“{}”或“set()”函数创建:
# 列表转Set
num_list = [1, 2, 3, 4]
num_set = set(num_list)
print(num_set) # {1, 2, 3, 4}
# 创建Set
fruit_set = {"apple", "banana", "orange"}
可以使用常见的集合操作,例如并集、交集和差集:
A = set([1, 2, 3, 4, 5])
B = set([4, 5, 6, 7, 8])
# 并集
print(A | B) # {1, 2, 3, 4, 5, 6, 7, 8}
# 交集
print(A & B) # {4, 5}
# 差集
print(A - B) # {1, 2, 3}
三、哈希冲突的解决办法
在哈希映射中,不同的key可能会经过哈希函数以后映射到数组的同一个位置上,这就是哈希冲突。当发生哈希冲突时,可以使用一下两种方法来解决:
1、拉链法:拉链法是一种将散列表中的每个单元都变成一个链表的方法。当出现了冲突,直接在对应的位置上插入一个新的元素即可。
# 哈希冲突的解决(拉链法)
class ListNode:
def __init__(self, key, val):
self.pair = (key, val)
self.next = None
class MyHashMap:
def __init__(self):
self.size = 1000
self.table = [None] * self.size
def put(self, key, value):
index = hash(key) % self.size
if self.table[index] is None:
self.table[index] = ListNode(key, value)
else:
node = self.table[index]
while node:
k, v = node.pair
if key == k:
node.pair = (key, value)
return
if node.next is None:
break
node = node.next
node.next = ListNode(key, value)
def get(self, key):
index = hash(key) % self.size
node = self.table[index]
while node:
k, v = node.pair
if key == k:
return v
node = node.next
return -1
def remove(self, key):
index = hash(key) % self.size
node = prev = self.table[index]
if not node:
return
if node.pair[0] == key:
self.table[index] = node.next
else:
node = node.next
while node:
if node.pair[0] == key:
prev.next = node.next
return
node, prev = node.next, prev.next
2、开放地址法:开放地址法是一种使用不同位置的单元来解决冲突的方法。可以通过线性探测、平方探测和再哈希等方式来选择下一个空闲位置。
# 哈希冲突的解决(开放地址法)
class MyHashMap:
def __init__(self):
self.size = 1000
self.keys = [0] * self.size
self.values = [0] * self.size
def put(self, key, value):
index = self.hash_function(key)
while self.keys[index] != 0 and self.keys[index] != key:
index = (index + 1) % self.size
self.keys[index] = key
self.values[index] = value
def get(self, key):
index = self.hash_function(key)
while self.keys[index] != 0:
if self.keys[index] == key:
return self.values[index]
index = (index + 1) % self.size
return -1
def remove(self, key):
index = self.hash_function(key)
while self.keys[index] != 0:
if self.keys[index] == key:
self.keys[index] = 0
self.values[index] = 0
return
index = (index + 1) % self.size
def hash_function(self, key):
return key % self.size
结论
Dictionary和Set在Python中的应用非常广泛,可以用来解决大量的问题。在哈希冲突的解决方案中,开放地址法比拉链法的实现方式更加高效,但也需要考虑到不同的解决方案对空间消耗的影响。