|
Çؽ¬(Hash)ÀÇ °³¿ä
|
|
¡á ÀûÀçÀ² - °³³ä : µ¥ÀÌÅÍÀÇ ¼ö /
Çؽ¬ Å×À̺íÀÇ Å©±â - ÀûÁ¤
ÀûÀçÀ²(¥ë) : üÀιý 1.0, °³¹æÁÖ¼Ò¹ý 0.5
¡á Àç Çؽ³ - °³¹æÁÖ¼Ò¹ý¿¡¼ ÀûÀçÀ²ÀÌ
0.5 ÀÌ»óÀÌ µÇ¸é ÀçÇؽ³ÇÑ´Ù. -
»õ·Î¿î TableSize = Á¾Àü TableSize * 2 º¸´Ù Å« ¼Ò¼ö
- »õ·Î¿î Çؽ¬ÇÔ¼ö : H(X) = X
mod »õ·Î¿î TableSize
¡á Çؽ³ÀÇ ¼öÇà ¼Óµµ : O(1) - °¡Àå
ºü¸¥ ¾Ë°í¸®ÁòÀÌ´Ù. - DB
µî¿¡¼ ÁÖ¿ä system tableÀº ¸ðµÎ Çؽ³À» »ç¿ëÇÑ´Ù.
¡á Lazy Deletion - Çؽ³¿¡¼´Â µ¥ÀÌÅÍÀÇ
»èÁ¦´Â »èÁ¦Çß´Ù´Â ¸¶Å©¸¸ ÇÑ´Ù. (info
field °ªÀ» Deleted·Î ¹Ù²Þ) -
½ÇÁ¦·Î »èÁ¦ÇÒ °æ¿ì ´ÙÀ½ µ¥ÀÌÅ͸¦ ãÀ» ¼ö ¾ø´Ù.
|