прикреплённый файл:emuhash.py к странице LecturesCMC/PythonIntro2017/07_Dicts

   1 #!/usr/bin/env python3
   2 '''
   3 Имитация хеш-таблиц
   4 Формат одного объекта:
   5     [количество занятых элементов, хеш-функция, таблица элементов]
   6 Незанятые ячейки заполнены объектом None
   7 '''
   8 # limit: 10
   9 # stdout: | less
  10 
  11 MINSZ = 8       # Minimal size
  12 MAXFULL = 50    # Percents full
  13 
  14 def Next(table, hsh):
  15     '''Повторное индексиование при коллизии'''
  16     return (hsh+1)%len(table[2])
  17 
  18 def Makehash(t):
  19     '''Создать хеш-функцию для таблицы t или для таблицы размера t'''
  20     Len = t if type(t) is int else len(t[2])
  21     def Hash(value):
  22         return hash(value)%Len
  23     return Hash
  24 
  25 def Init(size=MINSZ, seq=[]):
  26     '''Создать хеш-таблицу размера size из списка seq'''
  27     return Add([0,Makehash(size),[None]*size],*seq)
  28 
  29 def Add(table, *values):
  30     '''Добавить в таблицу table элементы values'''
  31     for value in values:
  32         if value is None:
  33             continue
  34         if len(table[2])<table[0]*100/MAXFULL:
  35             Enlarge(table)
  36         hsh = table[1](value)
  37         while table[2][hsh] is not None and value != table[2][hsh]:
  38             hsh = Next(table, hsh)
  39         if table[2][hsh] is None:
  40             table[2][hsh] = value
  41             table[0] += 1
  42     return table
  43 
  44 def Str(table):
  45     '''Строковое представление таблицы'''
  46     res = "===={}/{}\n".format(table[0],len(table[2]))
  47     def repr(i,v):
  48         '''Эелмент и его хеш или ..., если ячейка пуста'''
  49         if v is not None:
  50             hsh = table[1](v)
  51             coll = "collision " if hsh !=i else ""
  52             return "{:10} ({}{})".format(v, coll, hsh)
  53         else:
  54             return "..."
  55     res += "\n".join(repr(i,v) for i,v in enumerate(table[2]))
  56     res += "\n===="
  57     return res
  58     # то же самое в одну строку, слабонервным не читать:
  59     # return "===={}/{}\n".format(table[0],len(table[2]))+"\n".join("{:10} ({}{})".format(v, "collision " if table[1](v)!=i else "", table[1](v)) if v is not None else "..." for i,v in enumerate(table[2]))+"\n===="
  60 
  61 def Iter(table):
  62     '''Вернуть итератор по элементам таблицы'''
  63     return (e for e in table[2] if e is not None)
  64 
  65 def Enlarge(table):
  66     '''Увеличить таблицу в два раза'''
  67     # создадим новую таблицу и перепишем все её поля обратно в старую
  68     table[:] = Init(len(table[2])*2, table[2])[:]
  69     return table
  70 
  71 def Search(table, value):
  72     '''Проверить, содержится ли value в table'''
  73     hsh = table[1](value)
  74     while table[2][hsh] is not None:
  75         if table[2][hsh] == value:
  76             return True
  77         hsh = Next(table, hsh)
  78     return False
  79 
  80 if __name__ == "__main__":
  81     import random
  82     T = Init()
  83     for i in range(100000):
  84         action = random.choice(("add","search","failsearch")) if T[0] else "add"
  85         if action == "add":
  86             patt = random.randrange(1000)
  87             print("Add {}".format(patt))
  88             Add(T,patt)
  89             print(Str(T))
  90         elif action == "search":
  91             patt = random.choice(list(Iter(T)))
  92             print("Search for {}: {}".format(patt, Search(T, patt)))
  93         else:
  94             patt = random.randrange(1000)
  95             print("Search for {}: {}".format(patt, Search(T, patt)))