Algoritmlarni loyihalashtirish va tahlil qilish

1. Bo'lish usuli

Agar kkalit bo'lsa va mxesh jadvalining o'lchami bo'lsa, xesh funktsiyasi h()quyidagicha hisoblanadi:
h(k) = k mod m
Misol uchun, agar xesh jadvalining o'lchami bo'lsa 10va k = 112keyin h(k) = 112mod 10 = 2. ning qiymati mning vakolatlari bo'lmasligi kerak 2. Buning sababi, 2ikkilik formatdagi vakolatlari 10, 100, 1000, …. ni topganimizda k mod m, biz har doim pastki tartibli p-bitlarni olamiz.
agar m = 22, k = 17, u holda h(k) = 17 mod 22 = 10001 mod 100 = 01
agar m = 23, k = 17, u holda h(k) = 17 mod 22 = 10001 mod 100 = 001
agar m = 24, k = 17, u holda h(k) = 17 mod 22 = 10001 mod 100 = 0001
agar m = 2p bo'lsa, u holda h (k) = p m ning pastki bitlari

2. Ko‘paytirish usuli

h(k) = ⌊m(kA mod 1)⌋
qayerda,

• 
  kA mod 1kasr qismini beradi kA,
  
• 
  ⌊ ⌋zamin qiymatini beradi
  
• 
  Ahar qanday doimiydir. Qiymati 0 va 1 oralig'ida yotadi. Lekin, Knuth tomonidan Aoptimal tanlov taklif qilinadi.≈ (√5-1)/2
  

3. Universal xeshlash

Universal xeshlashda xesh funksiyasi kalitlardan mustaqil ravishda tasodifiy tanlanadi.

3.Amaliy qism.
# Python program to demonstrate working of HashTable

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)