Hash Table 1

Hash Table is an important data structure in computer science world. I have looked up several documents, books and articles about it. However, some are too abstract to understand and some are too detailed to digest all the concepts. Here, I would like to make it easier for understanding Hash Table. This article is intended for an introduction of Hash Table and is wrote in the way how I learned and understand the Hash Table from the very beginning, so that later you can quickly pick up other Hash Table knowledge further on your own.

Chapter 1 Set

---

First of all, A good usage of data structure enables you to have the following operations efficiently, such asadd or insert, remove or delete and look-up or find. In fact, we can go further and say that using Hash Table to execute these above operations is faster than Tree Set, which is also faster than Array.

Velocity:    Hash Table > Tree Set > Array

So Hash Table can provide better Time Complexity in Big O notation.
The smaller the number between brackets, the better time complexity is.
E.g. O(100) > O(log 100)

It also means how long it should take to find an element in these three data structure.

Array	Tree Set	Hash Table[1]
O(n)	O(log n)	O(1) / O(1+n/k) [2]

1. The sharp difference among them is because Tree Set requires maintaining sequence between elements, whiling Hash Table does not. We will have further discussion on the time complexity for Hash Table later. No worries!
2. k: number of buckets (Refer to WikiPedia)