Реферат по дициплине: «Структуры данных и алгоритмы»

2. Метод умножения

h(k) = ⌊m(kA mod 1)⌋,
где

• 
  kA mod 1 отделяет дробную часть kA;
  
• 
  ⌊ ⌋ округляет значение;
  
• 
  A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.
  

3. Универсальное хеширование

В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.

Где применяются

• 
  Когда необходима постоянная скорость поиска и вставки.
  
• 
  В криптографических приложениях.
  
• 
  Когда необходима индексация данных.
  

• # Реализация хеш-таблицы в Python

  
  
• 
  
• 
  hashTable = [[],] * 10
  
• 
  
• 
  def checkPrime(n):
  
• 
  if n == 1 or n == 0:
  
• 
  return 0
  
• 
  
• 
  for i in range(2, n//2):
  
• 
  if n % i == 0:
  
• 
  return 0
  
• 
  return 1
  
• 
  
• 
  def getPrime(n):
  
• 
  if n % 2 == 0:
  
• 
  n = n + 1
  
• 
  while not checkPrime(n):
  
• 
  n += 2
  
• 
  return n
  
• 
  
• 
  def hashFunction(key):
  
• 
  capacity = getPrime(10)
  
• 
  return key % capacity
  
• 
  
• 
  def insertData(key, data):
  
• 
  index = hashFunction(key)
  
• 
  hashTable[index] = [key, data]
  
• 
  
• 
  def removeData(key):
  
• 
  index = hashFunction(key)
  
• 
  hashTable[index] = 0
  
• 
  
• 
  insertData(123, "apple")
  
• 
  insertData(432, "mango")
  
• 
  insertData(213, "banana")
  
• 
  insertData(654, "guava")
  
• 
  
• 
  print(hashTable)
  
• 
  removeData(123)
  
• 
  print(hashTable)
  

5.Литература

1. WWW.intuit.ru

2. www.Codechick.io