Хэш функц

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

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

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

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

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

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

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

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

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

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

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);

}

Ангилал:Хэш