[理工] [資結]-成大100-電機

[love5566188 (I'dont kown)]

http://0rz.tw/MInEZ

想問一下Hash table問題

9.Given a hash table of 11 buckets , labbled from 0 to 10. Each bucket can
  hold one key. The hash function h(key) = key % 11.Chaining is used in the
  hash scheme.Now,Supose the hash is initially empty and then the numbers
  "3,41,15,36,74,58,91,45,48,64"are hashed sequentially into the hash table.

  (2)What are the average comparisons if each number of the sequence is
     looked up once?

     請問這題的average comparison是要比較甚麼?

  (3)Hashing 的worst case 是O(n)嗎?

  (4)要怎樣才能使Hashing達到O(logn)?


對Hashing不是很了解Orz
麻煩請高手解答了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 175.98.50.200
推 onlyeric23:3 所有都collision 4 用binary tree
→ onlyeric23:喔 AVL或紅黑
→ onlyeric23:2是指全部在裡面後各找一次平均要比較次數?
→ love5566188:請問(2)是帶入hash function,如遇一次collision就表示
→ love5566188:比較一次嗎?
→ onlyeric23:compare就是比對是否為輸入的key吧
→ love5566188:謝謝on大