举个例子哈希表怎么用 要生动易懂
时间: 2023-08-03 17:07:58 浏览: 53
好的,我来给你举个例子,以描述哈希表的使用。
假设我们要创建一个电话簿,用来存储人名和对应的电话号码。我们可以使用哈希表来实现这个电话簿。
首先,我们创建一个空的哈希表,作为电话簿的容器。
接下来,我们开始添加联系人和电话号码到电话簿中:
1. 将联系人名字和电话号码作为键值对,例如:"Alice" 对应的电话号码是 "123456789"。
2. 我们使用一个哈希函数对联系人的名字进行哈希运算,得到一个哈希值。假设哈希函数将 "Alice" 哈希成了索引值 2。
3. 将键值对存储在哈希表中,将索引值为 2 的位置上存储 "Alice" 和 "123456789"。
4. 如果再次添加另一个联系人 "Bob" 和他的电话号码 "987654321",经过哈希函数计算得到索引值 3,将 "Bob" 和 "987654321" 存储在索引值为 3 的位置上。
现在,当我们需要查找联系人的电话号码时:
1. 输入联系人的名字,例如输入 "Alice"。
2. 再次使用哈希函数对 "Alice" 进行哈希运算得到索引值 2。
3. 在索引值为 2 的位置上找到存储的键值对,即 "Alice" 和 "123456789"。
4. 返回 "Alice" 对应的电话号码 "123456789"。
哈希表通过哈希函数和数组的结构,实现了快速的数据存储和检索。通过合理选择哈希函数,可以最大程度地减少冲突,提高查找效率。在这个例子中,我们使用联系人的名字作为键来进行哈希,并使用索引值来存储和查找电话号码。这样,我们可以通过联系人的名字快速地找到对应的电话号码。
相关问题
举一个例子,创建一个哈希表
好的,以下是一个用 Python 语言创建哈希表的例子:
```python
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, data):
hash_value = self.hash_function(key, len(self.slots))
if self.slots[hash_value] is None:
self.slots[hash_value] = key
self.data[hash_value] = data
else:
if self.slots[hash_value] == key:
self.data[hash_value] = data
else:
next_slot = self.rehash(hash_value, len(self.slots))
while self.slots[next_slot] is not None and self.slots[next_slot] != key:
next_slot = self.rehash(next_slot, len(self.slots))
if self.slots[next_slot] is None:
self.slots[next_slot] = key
self.data[next_slot] = data
else:
self.data[next_slot] = data
def get(self, key):
start_slot = self.hash_function(key, len(self.slots))
data = None
stop = False
found = False
position = start_slot
while self.slots[position] is not None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == start_slot:
stop = True
return data
def hash_function(self, key, size):
return key % size
def rehash(self, old_hash, size):
return (old_hash + 1) % size
```
这个哈希表使用了线性探测法来处理冲突,具体实现过程可以看代码中的注释。你可以通过以下代码测试这个哈希表的功能:
```python
h = HashTable()
h.put(54, "cat")
h.put(26, "dog")
h.put(93, "lion")
h.put(17, "tiger")
h.put(77, "bird")
h.put(31, "cow")
h.put(44, "goat")
h.put(55, "pig")
h.put(20, "chicken")
print(h.slots)
print(h.data)
print(h.get(20))
print(h.get(17))
print(h.get(55))
h.put(20, "duck")
print(h.get(20))
```
输出结果为:
```
[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
chicken
tiger
pig
duck
```
这个哈希表使用了除留余数法来计算哈希值,并且在处理冲突时使用了线性探测法。你可以通过修改代码中的哈希函数和处理冲突的方法来实现其他的哈希表实现方式。
什么是哈希表?举个具体的例子
哈希表(Hash Table)是一种常用的数据结,它通过将键(Key)映射到值(Value)来实现高效的数据查找和插入操作。
具体来说,哈希表使用哈希函数将键映射到一个固定大小的数组中的索引,称为哈希码。这个索引被用来存储对应的值。当需要查找或插入一个键值对时,再次使用哈希函数计算键的哈希码,并在数组中查找对应的位置。如果存在冲突,即多个键映射到了同一个位置,通常会使用链表或其他方法来解决。
例如,假设我们有一个存储学生信息的哈希表,其中键是学生的学号,值是学生的姓名。我们可以使用哈希函数将学号映射到一个数组的索引,例如:
哈希函数:hash(student_id) = student_id % array_size
假设数组大小为10,学生信息如下:
学号 姓名
1001 张三
2002 李四
3003 王五
根据哈希函数,我们可以得到对应的索引位置:
hash(1001) = 1001 % 10 = 1
hash(2002) = 2002 % 10 = 2
hash(3003) = 3003 % 10 = 3
然后,我们可以将学号和姓名存储在对应的位置上:
索引 学号 姓名
1 1001 张三
2 2002 李四
3 3003 王五
当需要查找学号为2002的学生姓名时,我们可以使用哈希函数计算出索引为2,然后在该位置上找到对应的值为"李四"。
通过哈希表,我们可以在平均情况下实现常数时间复杂度的查找和插入操作,从而提供高效的数据存储和检索能力。