Хэширование
Напишем
программу, которая по значению ключа рассчитает число
«хэш».
Число рассчитывается так, чтобы значения поискового ключа
распределились среди всех возможных значений хэша равномерно.
#описание
элемента дерева
numHashLen=577
#количество возможных хэшей
from sys import argv
#для
ручного задания имени файла
class PHashNode:
def __init__(self, val = []):
self.val = val
def hash_(s):
#хэш-функция
global numHashLen
h = 0
for i in s:
h = h * 61 + ord(i)
return h%numHashLen
#создание
списков
countArr = [0 for _ in range(numHashLen)]
searchArr = [PHashNode() for _ in range(numHashLen)]
try:
#попытка получить имя файла из первого аргумента
fname = argv[1]
except IndexError:
fname = 'text1.txt'
with open(fname, 'r') as f:
#чтение из
файла и добавление в список
слов
for line in f:
for k in line.split():
searchArr[hash_(k)].val.append(k)
countArr[hash_(k)] += 1
print('\n'.join([str(i)+' '+str(countArr[i]) for i in
range(len(countArr))]))
#вывод количества
слов для каждого хэша
Хэш-функция для каждого символа умножает текущее значение
(переменная
h
) хэша, которое изначально для каждой строки равно нулю, на 61
и прибавляет числовой код символа (функция
ord
). К
примеру, числовое
представление "а" — 97, "€" — 8364. Функция
возвращает остаток деления
итогового значения на переменную
numHashLen
,
что ограничивает число
возможных значений.