Return to Answer

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables with buckets implemented as linked lists is $O(n)$, where $n$ is the number of different words that you have found.

This happends because in the simplest implementstions each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

If the number of words is much bigger than the number of buckets, the best choices are:

• implementing buckets as binary trees or as other hash tables (with other hash functions);
• using a Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

For more discussion about hash table performance, see: Hash table vs Balanced binary tree

From wikipedia:

For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.

[...]

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables with buckets implemented as linked lists is $O(n)$, where $n$ is the number of different words that you have found.

This happends because in the simplest implementstions each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

If the number of words is much bigger than the number of buckets, the best choices are:

• implementing buckets as binary trees or as other hash tables (with other hash functions);
• using a Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

For more discussion about hash table performance, see: Hash table vs Balanced binary tree

From wikipedia:

For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.

[...]

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables is $O(n)$, where $n$ is the number of different words that you have found.

This happends because each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

I think that the best data structure that you could use is the Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

From wikipedia:

For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.

[...]

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables with buckets implemented as linked lists is $O(n)$, where $n$ is the number of different words that you have found.

This happends because in the simplest implementstions each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

If the number of words is much bigger than the number of buckets, the best choices are:

• implementing buckets as binary trees or as other hash tables (with other hash functions);
• using a Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

For more discussion about hash table performance, see: Hash table vs Balanced binary tree

From wikipedia:

For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.

[...]

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables is $O(n)$, where $n$ is the number of different words that you have found.

This happends because each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

I think that the best data structure that you could use is the Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables is $O(n)$, where $n$ is the number of different words that you have found.

This happends because each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

I think that the best data structure that you could use is the Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

From wikipedia:

For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.

[...]

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.