Хэш функц

Хэш

Энэ хайлтын арга нь түлхүүр утганд арифметик үйлдлээр хувиргалт хийн өгөгдөл байрлах хүснэгтийн хаягийг гарган авч шууд ханддаг.

Хеш хаяглал нь түлхүүрийн утга тодорхой биш, ерөнхий тохиолдолд энгийн энэ арга дээр үндэслэгддэг

Үндсэн асуудал:

Хадгалсан элементүүдийн хувьд дараах үйлдлүүдийг хийдэг.

add new element	Шинэ элемент нэмэх
delete element	Элемент устгах
search a element by key	Элементийг түлхүүрээр хайх

Эрэмбэлээгүй массив буюу Unsorted array/

Элементүүдийг массивт эрэмбэлэлгүйгээр хадгалсанаар:

add	Хамгийн сүүлийн элемент болгож нэмэх
delete	Устгах мэдээллээ олоход Удаан, Нүдийг дүүргэхэд Хурдан
search	Дараалсан хайлт Удаан

Эрэмбэлсэн массив буюу Sorted array

Элементүүдийг массивт эрэмбэтэйгээр хадгалсанаар

add	Элементийг тохирох байранд нь оруулах. Элементүүдийг шилжүүлэх үйлдэл хийдэг тул Удаан
delete	Устгасны дараа хоосон үлдсэн зайг хэрхэн дүүргэх вэ гэсэн асуудал гардаг. Элементүүдийг шилжүүлдэг тул Удаан
search	Хоёртын хайлт Хурдан

Холбоост жагсаалт

add	Нэг л зангилаа руу ханддаг тул Хурдан
Delete	Устгасны дараа холбоосыг хэвээр үлдээхэд Хурдан боловч тухайн устгах зангилааг хайж олоход Удаан
search	Дараалсан хайлт Удаан O(n) �(Холбоост жагсаалт ашигласан үед элементүүд нь эрэмбэлэгдсэн байсан ч Хоёртын хайлтыг ашиглах боломжгүй юм.)

Хүснэгт байдалтай массив буюу хеш хүснэгт

Элементүүдийг индекс нь түлхүүрийг илэрхийлэх маш том массивт хадгалсан үед:

add – Маш хурдан

delete - Маш хурдан

search - Маш хурдан

Гэвч энэ нь маш их санах ойг зарцуулна. Байх боломжгүй.

Хеш функц

Энэ нь түлхүүрийг тухайн хязгаар доторх индекс рүү чиглүүлдэг. Зорилтот шаардлагууд: Тооцоолоход хялбар ба хурдан байх Тархсан байсан ч зөрчил үүсэх магадлал маш их тул зайлсхийх

function Hash(key: KeyType): integer; Hash гэдэг функц байна гэж төсөөлье. Энэ нь 1000 элементийн түлхүүр буюу key-ыг 0..999 гэсэн бүхэл тоо руу чиглүүлдэг. (Ингэхдээ 2 ялгаатай түлхүүрт ижил дугаар олгодоггүй.) Perfect Hash function-тай Хэш хүснэгт:

Доорх боломжыг олгохоор индексийг үүсгэдэг функцыг perfect буюу төгс функц гэдэг.

add – Маш хурдан O(1)

delete - Маш хурдан O(1)

search - Маш хурдан O(1)

Төгс хеш функц гэдэг нь түлхүүр бүрт ялгаатай утга буюу индексийг боловсруулж өгдөг.

Гэвч энэхүү функцыг загварчлахад маш хүндрэлтэй (боломжит түлхүүрийн хэмжээ нь их үед)

Хуваах арга:

Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд m анхны тоо байх шаардлагатай. Эндээс H функцыг H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцад шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.

Зөрчил:

Ерөнхийдөө зөрчилөөс зайлсхийж чаддаггүй Collision resolution – 2 ялгаатай түлхүүр ижил тоогоор илэрхийлэгдэх явдал хэр их тохиолдож байгаа нь.

       H(‘0012345’) = 134
       H(‘0033333’) = 67
       H(‘0056789’) = 764
       …
       H(‘9903030’) = 3
       H(‘9908080’) = 3

Дараах тохиолдолд зөрчилөөс зайлсхийх боломжтой:

Түлхүүрийн тоо > Хеш хүснэгтийн хэмжээ

Зөрчилөөс зайлсхийхийн тулд:

Хеш хүснэгтийн мөр бүрд түлхүүрүүдийг байрлуулахаар сонгож чаддаг хеш функцийг сонгох.

2 түлхүүрт Хэшийн ижил орон зайг тодорхойлсон утга гарсан тохиолдолд зөрчил үүснэ. Түүнийг шийдэх 2 арга байдаг:

Hashing with Chaining:

Хэш хүснэгтийн үүр бүр нь ижил индекстэй түлхүүрүүд бүхий бичлэгүүдийн холбоост жагсаалтыг заасан заагчыг агуулдаг

Hashing with Open Addressing:

Хэш хүснэгтийн үүр бүр нь зөвхөн ганц түлхүүрийг агуулдаг. Хэрэв шинэ түлхүүр нь мэдээлэл хадгалагдсан үүр рүү чиглүүлэгдвэл (индекс нь давхардвал) хоосон орон зайг олтол хүснэгтийн орон зайнуудыг шалгадаг.

Нээлттэй үүртэй хеш хүснэгт

Bucket – Хеш хүснэгтийн үүр буюу орон зай

Open-bucket hash table: Хадгалах орон зай нь Ганц өгөгдлийн элементэд л зориулагдсан байдаг

Түлхүүрийг хувиргасны дүнд home bucket буюу хадгалах үүр гардаг

Хаалттай үүртэй хэш хүснэгт

Closed-bucket hash table: Үүр буюу хадгалах орон зай нь өгөгдлийн элементүүдийн цуглуулгад зориулагдсан байдаг

Hash функцын жишээ

int hash(char * key)

{

int val = 0;

while(*key != '\0')

{

val = (val << 4) + (*key);

key++;

}

return val;

}

int compress(int index, int size)

{

return abs(index % size);

}