Cuckoo Hashing for Undergraduates

Rasmus Pagh

IT University of Copenhagen
March 27, 2006

Abstract

This lecture note presents and analyses two simple hashing algorithms:“Hashing with Chaining”, and “Cuckoo Hashing”. The analysis uses only very basic (and intuitively understandable) concepts of probability theory, and is meant to be accessible even for undergraduates taking their first algorithms course.

1. Introduction

A dictionary is a data structure for storing a set of items (e.g., integers or strings), that supports three basic operations:

Lookup(x) which returns true if x is in the current set, and false otherwise;
Insert(x) which adds the item x to the current set if not already present;
Delete(x) which removes x from the current set if present.

A common variant is to associate some information with each item, which is returned in connection with lookups. It is a simple exercise to augment the algorithms presented here with this capability, but we will describe just the basic variant.

如何能寫出一篇好論文?

論文的其中一項功用就是讓大家了解你的研究成果。
而如何寫好論文，就是另一個重要的課題。

現在把這些年來的經驗總結歸納如下：科研論文三部曲﹣看文獻、做實驗、寫論文
一.看文獻（如果不太熟習英文的學術語言，不要勉強自己。可以先中文，後英文。先掌握個大概。）:
就我的經驗是先讀比較大量的文章，至少10篇以上，當然，一般只能讀懂很少的一部分。但這時候，你能從中找到自己感覺最不錯的一篇文章，再讀一遍，查處所有不懂單詞的精確意思，然後再精讀。其實很多時候，我們讀文獻都太浮躁了，只求數量走馬看花。數量可觀，但效果很差。

1.先對專業知識進行足夠了解後，再看英文文獻.
找一本中文經典的書籍，僅看某一節你感興趣或與你相關的內容，然後先找一兩篇英文的綜述（review) 認真閱讀一下。
2.看英文文獻，不一定數量多，可以精選相關的文獻精讀，最關鍵是要讀懂.
不會的單詞可上GOOGLE查一查。也許你讀第一遍需要花兩天，你過兩天再讀第2 遍時，你也許只要一天；然後你再讀第3遍時也許你只要半天！然後你一定會真正發現讀英文文獻的快感！
*3.適當的追查引文，找到最初解釋，不能片面理解.
*4.做好記錄，方便以後查找.
*5. 抓住文獻要點看

• 1. 作者所做實驗的內容
• 2. 實驗方案及所用到的方法、手段
• 3. 實驗結論與分析
• 4. 實驗中存在的不足 (按: 找到人家實驗中存在的問題與不足，也就找到了自己努力的方向)
• 5. 作者的實驗思想 (按: 當你透過字裡行間把握了作者的實驗主導思想，就可以對實驗方案進行高屋建瓴地分析與取捨了)

閱讀文獻的第一個境界－有用的才是金子

http://blog.tech110.net/?uid-10696-action-viewspace-itemid-34252
首先我要說，科研(research)的很大一部分就是和文獻打交道。

就像學習武功，要有密笈之類的東西，這就是文獻。(當然，像Nature, Science, Cell這類期刊，就是九陰九陽易筋經之類的檔次，研讀者一般是高僧或者武學奇才這類人，對於一般人而言，就是自己研究領域中的某幾類期刊而已。)所以，有明確具體目的，或者有個大體方向，就可以檢索和下載文獻（當然，檢索和下載都有一些技巧，看看小木蟲，加上自己的實踐和摸索，都會有較大的提高）

隨便說一句，雖然有師兄，但是，師兄或者搞其它的方向，或者，很難告訴你那一篇文獻是金子，含金量最高。所以，檢索一般是大量的，工作一般是機械的，心情一般是孤獨的。這就像是蹲馬步的初始階段。

“對你最有用的，最有幫助的，可能僅僅是一篇文章，或者是一篇文章的某一段”。

根據線索、關鍵字下載了大量的PDF，下面就要進行披沙揀金的工作了----尋找有用的那一篇或那一段。其實，當你找到的時候，你已經有了一定的功夫，有了新的靈感，新的方案，新的收穫。

關於閱讀英文文獻的一點體會

要在高起點上開展學術研究，閱讀英文原文是不可或缺的環節。英文文獻閱讀的重要性不需贅述，國內多數理工科院校的研究已經實現了和國際的接軌，管理和經濟學科相對滯後，但是部分團隊已經走在前列。

中文文獻看多了之後就會發現很多內容似曾相識，英文文獻在內容的廣度和深度方面更勝一籌。閱讀英文文獻的目的不是為了論文增加幾個參考文獻而看上去好看，當然國內有些人是這麼做的，更有甚者為了增加英文參考文獻而引用二手或者三手文獻，在轉引過程中漏洞百出。廣泛閱讀英文文獻是提高綜合能力及水平，優化知識結構，轉換思維方式，拓展研究視野的必由之路，當然最重要的是將國際先進和中國實際相結合。

（1 ）英文原文讀不懂怎麼辦？

其實我以前也根本沒讀過原文，也看不懂。這兒有個好辦法：找一本中文經典的書籍，僅看某一節你感興趣或與你相關的內容，然後先找一兩篇英文的綜述（review) 認真閱讀一下，不會的單詞可用金山詞霸查一查，也許你讀第一篇文章需要花兩天，你過兩天再讀第2 遍時，你也許只要一天；然後你再讀第2 篇時也許你只要半天！然後你一定會真正發現讀英文文獻的快感！（引用）

我和這位作者有相同的體會，剛開始閱讀的時候可能有些困難，當你經過一個時期的訓練之後，就會很快進入狀態，並且感覺受益良多。

抓住要點看文獻(PAPER)

http://blog.tech110.net/?uid-10696-action-viewspace-itemid-34253
權威之所以權威，是因為人家工作做得早，做得多，讀他們的文章，站在巨人的肩膀上！
如何看文獻，各位網友們已經紛紛道出了自己的心得體會。

我在看文獻的過程中，始終注意抓住五個要點。這五個要點是—— 
1. 作者所做實驗的內容
2. 實驗方案及所用到的方法、手段
3. 實驗結論與分析
4. 實驗中存在的不足
5. 作者的實驗思想

在這五個要點中，後兩個更加重要，尤其是最後一個：找到人家實驗中存在的問題與不足，也就找到了自己努力的方向；當你透過字裡行間把握了作者的實驗主導思想，就可以對實驗方案進行高屋建瓴地分析與取捨了。

抓住這五個要點，對於想在短時間內快速了解某方面工作現狀來說，更是作用巨大；
對於寫綜述文章來說，也是非常有效的手段。所以，總結起來，這種方法的特點就四個字：簡便，高效！呵呵，這僅是個人感受，各位若不認同也別批哦，俺臉皮薄。歡迎大家聊一聊自己的方法，互相促進一下！

很有用的word排版教學(適合論文寫作)

就是底下這個blog:講得很詳細，雖然圖片有些模糊看得眼睛會很痠 http://maymaple.pixnet.net/blog/post/19079790
=========================================================
昨天(6/22)研究很久，因為Office 2007的選項跟舊版差滿多的，花了不少時間，所以決定用閒暇時間來慢慢完成這篇分享。步驟大致照著前一篇題到橘色舞圈圈的分享，圖檔之類的細節會慢慢補上。
PS. 不想看文字可以直接看圖檔→→用Office2007word排版

使用Word 2010寫論文

使用Word 2010寫論文，善用Word 2010內建、好用的功能，可以快速完成論文的格式設定，節省書寫論文的時間，達到事半功倍的效果。現在將已經發表的文章中，關於使用Word 2010書寫論文需要使用的功能彙整並做簡單的使用說明，方便大家參考使用：

1. Word 2010「大綱模式」設定論文的格式(手動編號)：在書寫論文之前，先使用「大綱模式」，建立章節的階層目錄，設定各階層與本文的格式，再書寫論文，可以節省很多時間。本文說明，如何以「大綱模式」，手動輸入章節編號的方式設立含章、節、目等三個階層的論文格式。

Oral Presentations Skill

The project presentation is assessed in general both on content and delivery to ensure that the student is able
to communicate project work done that is of a standard worthy of an honours degree. The project presentation will be graded according to five specific assessment outcomes.

Assessment Outcome:  
Content (To include Q&A):
-Relevance  25%
-Accuracy  25%
Delivery:
-Organization, preparation and effectiveness of delivery 25%
-Time management, style, pacing and body language 25%


The "magic" ingredients in giving a good presentation tend to be preparation, enthusiasm and confidence.
Some tips for good presentation technique include the following:

Prepare properly formatted transparencies (do not present transparencies which are direct photocopies of the project report).

• When using transparencies, do not try to put too much information on a single sheet. Consider using nothing less than 16-point print. 
• Try to schedule some periods in the presentation to communicate directly with the audience (making eye contact) without the aid of the white board or transparencies. 
• Consider very carefully whether a "live" demonstration of the project is necessary. 35 mm slides or a video-tape are much less likely to cause problems or delays during the presentation. 
• Attempt to understand and give comprehensive answers to any questions that are asked at the end of the presentation.  Do not give an answer to a question that was not asked! 

研究方法與進行步驟

根據前文"何謂方法(Method)與方法論(Methodology)"的引申

http://140.131.24.185/net/New-E-NET-02/G.Project/F-02.htm

4.1研究方法與進行步驟
(1) 理論基礎與研究架構
把看似無意義的「資料(data)」加以分析整理，讓它成為有意義的「資訊(information)」，這是推理的能力；把資訊再加以整理歸納就形成有用的「知識 (knowledge)」，把相關的知識加以靈活運用就形成「智慧 (wisdom)」。

就數位典藏創意學習而言，設計可以分成：
擷取文化風格特色(推理)、形成設計概念模式(知識)，與完成文化產品設計(智慧)三個階段。

本研究方法基本上延續加值(add-valued)模式為架構。就數位典藏的文化創意學習而言，
把典藏文物的原始「資料(data)」加以分析整理，讓它成為有意義的文物「資訊(information)」，這是推理的能力；
把資訊再加以整理歸納，形成有用的文化「知識 (knowledge)」，這是學習知識的方法；
把相關的知識加以靈活運用就形成人類的「智慧 (wisdom)」結晶，這是應用知識解決問題的能力；而這整個過程是創意學習的教育目的。

Getting Start a Final Year Project

http://final-year-projects.com/index.htm
一個好正GE網，教你由頭到尾點HANDLE個FYP，
點開始、處理SOURCE、點PRESENT...etc.
咁當然LA，個外殼比左你，但個涵就要靠自己了。

ref:
http://gian3211.blogspot.hk/2013/04/methodmethodology.html

何謂研究(Research)

http://tkbpeter.pixnet.net/blog/post/8162006
研究(Research)：
簡而言之，就是架構知識殿堂的方法
從事研究的人，就好像是 砌學術殿堂的磚的工人
而後人之所以能夠看的更遠，只因為他們站在巨人的肩膀上。 

關於研究的定義版本很多，以下舉我個人認為較為簡單明瞭的定義來跟大家說明：

Grinnell(1993)認為 ：
將研究的單字拆解為re-search ，意指一次再一次地 仔細 檢查、試驗或探究 。
也就是在某一知識領域中，小心且有系統地調查，以便發現事實真相並建立原則。

Kerlinger & Lee (2000)認為研究還要包括以下特性︰ 

為何要學習研究方法?

http://tkbpeter.pixnet.net/blog/post/7881950
前兩個星期 一位考上同學來信問到如何做研究。
由於這個題目實在太大，無法用三言兩語來做回應 ，
所以我打算慢慢整理以前上研究方法課程的內容，
並將這些內容整理成文章po在網路上與同學分享。
一開始，我們先聊聊「為何要學習研究方法?」 

----------------------------------------------------------------------
先講個故事
在古埃及、希臘與羅馬時期
當時的人們認為心臟主導了人類的精神與情感
但他們並未曾解剖過活體
所以沒有機會觀察到靜脈與動脈中血液流動的情形
於是人們由屍體中發現
進出肝臟的靜脈總是漲滿著血液
因此他們認為血液是由肝臟所製造
而心臟存在的目的
就是將充滿活力的「精神」
注入到通過心臟的血管中

如何開始學習研究方法

大學生要學習研究方法的內容:

粗略大致可分成

1.研究方法理論

(何謂研究、方法論、研究方法、文獻回顧、研究設計、抽樣設計...等)

2.研究方法工具(理論)

(統計、多變量分析、計量(迴歸)...等)

3.研究方法工具(軟體)

(SAS、SPSS、質化分析軟體...等)

另外還有

4.研究實務

(找老師、做研究、投稿...等)

以上這些內容，除了基礎統計大部份同學學過之外，其他內容同學幾乎都要從頭學起。

何謂方法(Method)與方法論(Methodology)

在說明了何謂「研究」之後
接下來我們來談一下何謂「方法」(Method)
(這樣大家就會對「研究方法」有一簡單的認識了 XD)

簡單來說
「方法」是指「蒐集資料、進行推論、解釋與預測的工具或技巧」 (談的是how) 
e.g. 自然科學家透過「顯微鏡」來觀察生物細胞
而社會學家則使用「問卷」來調查大眾對某件事情的看法

因應觀察對象的不同，會使用不同的工具。
但背後都是利用「觀察」這個方式 來蒐集資料 。

另一個與「方法」相關的名詞叫做「方法論」(Methodology)
「方法論」指的是「研究『方法』」的理論，也是研究過程的哲學。

方法論所涉及的主要是方法的基本假設、邏輯與原則 (談的是What、Why) 

如何看英文文献

       如果你时间有限，建议读懂摘要 (Abstract), 在此基础上注重看结论(Result)和 讨论“Discussion” (有些文献中称为 Conclusion)。在写综述时，有很多语句可以从这些段落中借鉴。你文献一多，总结自然也就出来了。不会太难。

      先看摘要（看文章是否有要看的价值），再看方法，最后看讨论，尤其是方法，看不懂后面就更加看不懂了。边看边做笔记。把重要的划出来，看完一段后试试看能不能用自己的话说出来。

如何阅读英文文献（转载）

NO.1

中科院大博士是如何进行文献检索和阅读的（好习惯受益终生）  一.如何进行文献检索  我是学自然科学的，平时确实需要不少外文文献，对于自然科学来讲英文文献检索首推Elsevier，Springer等。虽然这些数据库里面文献已经不算少了。但是有时还会碰到查不到的文献，而这些文献的数据库我们所在研究所或大学又没有买，怎么办？我基本通过以下向个途径来得到文献。  
1．首先在Google 学术搜索里进行搜索，里面一般会搜出来你要找的文献，在Google学术搜索里通常情况会出现“每组几个”等字样,然后进入后，分别点击，里面的其中一个就有可能会下到全文，当然这只是碰运气，不是万能的，因为我常常碰到这种情况，所以也算是得到全文文献的一条途径吧。可以试一下。同时,大家有没有发现,从Google学术搜索中,还可以得到一些信息,

http://scholar.google.com.hk/

Google学术搜索中会显示出你搜索文章的引用次数,不过这个引用次数不准确,但是从侧面反应了这篇文章的质量,经典文章的引用次数绝对很高的.同时如果你用作者进行搜索时,会按引用次数出现他写的全部的文章,就可以知道作者的哪些文章比较经典,在没有太多时间的情况下,就可以只看经典的.  

科研論文三部曲﹣看文獻、做實驗、寫論文

發表科研論文幾乎是所有研究生乃至科研院所人員的主要工作之一，這有利於大家了解你的研究進展，而如何寫好論文，是另一個重要的課題。
現在把這些年來的經驗總結歸納如下：
一.看文獻（先中文，後英文）
1.先對專業知識進行足夠了解後，再看英文文獻.
2.看英文文獻，不一定數量多，可以精選相關的文獻精讀.
3.適當的追查引文，找到最初解釋，不能片面理解.
4.做好記錄，方便以後查找.

二.做實驗（先模仿，後創新）
1.找已成功的案例，模仿實驗，熟悉實驗過程.
2.對實驗步驟、操作、條件熟悉後，開始自己的試驗.
3.先作計劃，設計好實驗，不能盲目.
4.做好實驗記錄，現象、結果等記錄詳細、明了，以便以後查找原因或對比.
5.經常把系列實驗數據總結，進行階段性對比及計劃.

三.寫文章
1.列出文章提綱，按部分、分塊集中寫.
2.有針對性，圍繞數據規律、實驗現象找文獻，解釋實驗數據規律、實驗現象.
3.創新性、系統性、實用性的東西是必要的.
總之，成果是平時實驗積累起來的，沒有捷徑。

关于阅读英文文献的一点体会-（3）阅读英文文献需要持之以恒

http://blog.tech110.net/?uid-2490-action-viewspace-itemid-31423

英文文献的阅读需要持之以恒。不只是为了写文章或者做项目才去检索和阅读文献，而是需要贯穿于研究生学习的全过程。这是选题和把握前沿领域的重要途径，同时也可以提高自己的英文阅读能力。当然，文献阅读的效果不会在短期内显现出来，不能说读了几篇英文文献就怎么样，但是当你把英文文献作为主要阅读对象时，可能会渐渐发生变化。

有些中文文献存在不足之处，例如，数据可靠性差、观点（判断）不可检验；方法运用存在缺陷；文献综述不全面等。对于多数社会科学而言我们最终还是要研究中国问题，中文文献是入门的基础，国内重要期刊的文章仍然需要有一个全面的了解。

关于阅读英文文献的一点体会﹣（2）我们需要阅读什么样的文献？

http://blog.tech110.net/?uid-2490-action-viewspace-itemid-31423

虽然英文文献总体上水平比较高，但并不是所有的文献都值得阅读，阅读文献的前提是能够检索到对你有价值的文献。

第一步知道如何检索文献，现在学校的英文数据库平台很多，可以尝试检索和合理利用。当然机器检索不能完全找到和主题相关的文章，需要扩大检索范围，然后认真阅读摘要，筛选和自己工作相关的文献。

第二步知道如何确定文章的价值，这和中文文献阅读具有相似之处，首先是重要期刊的文章，其次是著名学者的文章。例如在国家创新体系领域，Lundvall\Freeman\Nalson\OECD\Porter等这些重要的作者和机构的文献是必读的，不仅要精读他们的经典文献，而且要追踪其最新研究成果，包括工作论文、讨论稿等。通过对重要作者的研究和经典文献的阅读能给你打开一扇门，让你进入一个由核心作者、相关作者、主要期刊和主要研究机构形成的学术网络。

关于阅读英文文献的一点体会﹣（1）英文原文读不懂怎么办？

http://blog.tech110.net/?uid-2490-action-viewspace-itemid-31423

其实我以前也根本没读过原文，也看不懂。这儿有个好办法：找一本中文经典的书籍，仅看某一节你感兴趣或与你相关的内容，然后先找一两篇英文的综述（review)认真阅读一下，不会的单词可用金山词霸查一查，也许你读第一篇文章需要花两天，你过两天再读第2遍时，你也许只要一天；然后你再读第2篇时也许你只要半天！然后你一定会真正发现读英文文献的快感！（引用部分）

我和这位作者有相同的体会，刚开始阅读的时候可能有些困难，当你经过一个时期的训练之后，就会很快进入状态，并且感觉受益良多。

一直不会看外文文献，学学人家

http://chenyazhi2108.blog.163.com/blog/static/8362506420109994442717/

本人英语基础不好，没过六级，所以在硕士的时候基本上看的外文文献很少，现在想想很后悔，2年的时间少学了很多东西。上了博士，自己给自己的定位也高一些了，开始打算硬着头皮咬着牙很不情愿的也要多看些外文文献，一开始看比较慢，有些很难理解，到现在大约仔细阅读了100篇外文文献，泛读了100篇外文文章，受益匪浅，现在基本不怎么看中文的了，确实也觉得外文的质量就是高（也有凑数的烂文章），现在自己写外文的也很顺手了。谈几点自己的体会。 
1.先找5篇跟自己论文最相关的外文文章，花一个月的时间认认真真的看，反复看，要求全部读懂，不懂的地方可以和同学和老师交流一下。一个月以后你已经上路了。