|
Çؽ¬(Hash)ÀÇ °³¿ä
|
|
- Æúµù¹ý : Å° °ªÀ» 2Áø¼ö·Î º¯È¯, 2~3
µîºÐÇÏ¿© ADD/XOR ÇÔ. K
= 7632 = 000111012 => ADD : 1110, XOR
: 1100 - ±â¼öº¯È¯¹ý : ´Ù¸¥
Áø¹ýÀ¸·Î °è»êÇÔ. ¿¹, H_Size = 10000 ÀÏ ¶§, key
= 100105 => 115 + 112 + 5 =
161177 => 1177 -
ÀÚ¸´¼öºÐ¼®¹ý : Å° °ª Áß °°Àº ¼ýÀÚ°¡ ¸¹Àº ÀÚ¸®´Â Á¦°ÅÇÑ´Ù.
025452184,
02543678, 025458171 => 2184, 3678, 8171 ¡á Ãæµ¹
ÇØ¼Ò (Collision Resolution) -
üÀιý : °°Àº ÁÖ¼Ò·Î Çؽ¬µÇ´Â µ¥ÀÌÅÍÀÇ ¿¬°á¸®½ºÆ® À¯Áö
- °³¹æÁÖ¼Ò¹ý : Ãæµ¹ ¹ß»ýÇϸé
´ÙÀ½ ºó¹æÀ» ã¾Æ ³ÖÀ½, ¹è¿ »ç¿ë
¡á °³¹æÁÖ¼Ò¹ýÀÇ ÁÖ¼Ò »êÃâ °ø½Ä -
Hi(X) = (Hash(X) + F(i)) mod Table_Size, X = Å° °ª
- ¼±Çü°Ë»ö¹ý (Linear Probing)
: F(i) = i - ÀÌÂ÷°Ë»ö¹ý (Quadratic
Probing) : F(i) = i2 -
ÀÌÁßÇؽ³¹ý (Double Hashing) : F(i) = i x H'(X)
|