-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash_table.py
147 lines (128 loc) · 6.53 KB
/
hash_table.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import random
import time
DELETED = 'deleted' # для обработки удалений элементов
class Node:
def __init__(self, key = None, value = None):
self.key = key
self.value = value
def __str__(self):
return 'key: {}, value: {}'.format(self.key, self.value)
def __eq__(self, other):
if other == DELETED:
return False
return self.key == other.key
class HashTable:
def __init__(self, size, hash_type=None):
self.size = size
self.current_size = 0
self.table = [None for _ in range(self.size)]
self.hash_type = hash_type
self.k = 3 # фиксированный интервал между ячейками при линейном пробировани
#Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо,
# чтобы k было взаимно-простым с размером хеш-таблицы.
self.c1 = 3 # \
# | коэффициенты при квадратичном пробировании
self.c2 = 2 # /
self.choose_hash_type()
def choose_hash_type(self):
if not self.hash_type:
print('Выберите функцию для последовательности проб: linear, quadratic, double')
hash_type = input()
if hash_type in ['linear', 'quadratic', 'double']:
self.hash_type = hash_type
else:
print('По умолчанию выбрано линейное пробирование')
self.hash_type = 'linear'
else:
return
def resize(self):
self.table += [None for _ in range(self.size)]
self.size *= 2
def hashing(self, i, hash_value=None, hash_value_first=None, hash_value_second=None):
if self.hash_type == 'linear':
return self.linear_hashing(hash_value, i)
elif self.hash_type == 'quadratic':
return self.quadratic_hashing(hash_value, i)
elif self.hash_type == 'double':
return self.double_hashing(hash_value_first, hash_value_second, i)
def linear_hashing(self, hash_value, i):
cell_number = (hash_value + (i * self.k) % self.size) % self.size
return cell_number
def quadratic_hashing(self, hash_value, i):
cell_number = ((hash_value + self.c1 * i) % self.size + self.c2 * pow(i, 2, self.size)) % self.size
return cell_number
def double_hashing(self, hash_value_first, hash_value_second, i):
cell_number = (hash_value_first + (i * hash_value_second) % self.size ) % self.size
return cell_number
def hash_function(self, key):
return key % self.size
def second_hash_function(self, key):
return 7 - (key % 7)
def insert(self, key, value):
idx = 0
if self.hash_type != 'double':
hash_value = self.hash_function(key)
else:
first_hash_value = self.hash_function(key)
second_hash_value = self.second_hash_function(key)
while True:
if self.hash_type != 'double':
cell_number = self.hashing(idx, hash_value=hash_value)
else:
cell_number = self.hashing(idx, hash_value_first=first_hash_value, hash_value_second=second_hash_value)
if not self.table[cell_number] or self.table[cell_number] == DELETED: # если нет такого ключа или он был удален
self.table[cell_number] = Node(key, value)
self.current_size += 1
if self.current_size >= 0.66 * self.size:
self.resize()
break
else:
if self.table[cell_number].key == key:
self.table[cell_number].value = value
break
idx += 1 #ищем дальше свободное место
def delete(self, key):
if self.current_size == 0:
#print('Хеш-таблица пустая. Элемент {} нельзя удалить'.format(key))
return
if self.hash_type != 'double':
hash_value = self.hash_function(key)
else:
first_hash_value = self.hash_function(key)
second_hash_value = self.second_hash_function(key)
for idx in range(self.size):
if self.hash_type != 'double':
cell_number = self.hashing(idx, hash_value=hash_value)
else:
cell_number = self.hashing(idx, hash_value_first=first_hash_value, hash_value_second=second_hash_value)
if self.table[cell_number] and self.table[cell_number] != DELETED and self.table[cell_number].key == key: # если ключ найден
self.table[cell_number] = DELETED
self.current_size -= 1
return
#print('Элемент с ключом {} не удален, так как не найден в хеш-таблице'.format(key))
def search(self, key):
if self.current_size == 0:
#print('Хеш-таблица пустая. Элемент {} отсутствует'.format(key))
return
if self.hash_type != 'double':
hash_value = self.hash_function(key)
else:
first_hash_value = self.hash_function(key)
second_hash_value = self.second_hash_function(key)
for idx in range(self.size):
if self.hash_type != 'double':
cell_number = self.hashing(idx, hash_value=hash_value)
else:
cell_number = self.hashing(idx, hash_value_first=first_hash_value, hash_value_second=second_hash_value)
if self.table[cell_number] and self.table[cell_number] != DELETED and self.table[cell_number].key == key: # если ключ найден
#print('Элемент найден в хеш-таблице: {}'.format(self.table[hash_value]))
return self.table[cell_number]
#print('Элемент с ключом {} не найден в хеш-таблице'.format(key))
return None
def __str__(self):
str_table = []
for i in range(self.size):
if self.table[i]:
node_info = [str(self.table[i]), 'cell: {}'.format(i)]
str_table.append(node_info)
return 'Hash table size: {} (current size: {}), hash table: {}'.format(self.size, self.current_size, str(str_table))