0
$\begingroup$

Using probing, is it possible for for a hash table's load factor to exceed 100%? I don't too much about Hash Tables. Is this possible?

$\endgroup$
2
$\begingroup$

The load factor of a hash table is defined as:

$$\lambda = \frac{n}{k}$$

where $n$ is the number of items stored in the table and $k$ is the number of buckets. So the load factor is greater than 1 if there are more entries than buckets.

Storing more than one entry in a bucket is very common. The most familiar example is separate chaining (e.g. a linked list of entries in the bucket), used for in-memory hash tables.

For disk-based hash tables (as found in database servers or some file systems or file management systems), a "bucket" is typically a page (possibly a disk page or a virtual memory page) in size, so for typical use cases, you can easily fit more than one item into it. A scheme such as extendible hashing is typically used to manage buckets in a way that minimises disk traffic.

$\endgroup$
0
$\begingroup$

In theory, yes. As far as were told in practice, no (SHORT ANSWER AT BOTTOM).

A hash table's load factor is defined, as Pseudonym states, as:

$LF = \frac{elements}{array.length}$.

That is, $LF$ is the number of elements present in the array by the length of the array itself.

But for any person who may stumble across this and have no idea what Hash Tables are, perhaps we should be clear exactly what a Hash Table entails...

Hash Tables are nothing more than arrays that store elements.

We usually have an array of length $n$. Each array index will usually hold elements of some type. When we add elements to the array, we determine where they will go based on the hashCode() of that element. We take the hashCode() and mod it by the length of the array. Whatever this number is will be the index we store our element in.

Now one of the major problems of hash codes is that there are a finite amount of hash codes, so we're bound to have two objects "collide" - that is, both objects will have the same hash code and end up at the same array index. In this case, we develop "collision resolution" strategies to counteract this. These strategies are, but not limited to:

COLLISION RESOLUTION STRATEGIES -

  1. External/separate chaining : Every array slot can hold a List, traditionally a Linked List of elements of some given type. This allows us to store/add multiple elements with the same hash code in the same index by adding to the List present in that index. You can imagine each List of elements as a chain of elements, hence the terminology.

  2. Probing (Linear) : In this strategy, we restrict our Hash Tables to hold only one element at any given index. If we find that the initial index provided by element.hashCode % array.length is full, we iterate through the array (modding the number by array.length each time, to restrict us to the array indices only) until we find an empty spot and place our element there.

  3. Probing (Quadratic) : Similar to linear probing, except instead of iterating linearly over the array until we find an empty spot, we add exponentially to the initial given index (1, 4, 9, etc...) and mod the number by array.length, and find an empty spot that way.

Now, how does this affect Load Factor? Every time we add an element successfully, we increase the load factor because the number of elements goes up by one.

Now, according to a resource by University of Texas from one of their Data Structure classes, one can have the Load Factor exceed 1 (exceed one hundred percent). Imagine an array of length 5 where each index holds a list of five elements. Clearly:

$LF = \frac{25}{5} = 5$

I only just found out it's okay to have the load factor exceed one in this case as performance apparently does not decrease. You learn something new everyday!

However, as we were taught in our data structures course, we focused on the implications of load factor as it pertains to probing collision resolution strategies.

It makes sense that the more we tend towards 1 with LF, the slower our retrieval, addition, and removal times may be. Consider that for any given element we're trying to remove, we are not guaranteed that that element is in the spot we've initially calculated - if not, we need to potentially iterate through the entire array to find/remove the element, which is of course O(n).

In order to counteract this, we traditionally institute some bound on how large the Load Factor can be. I've seen it be .75, but it can be lower. It's mostly always above 1/2, at least.

If the load factor increases past a certain bound, this triggers an immediate resizing of the array (usually doubling the size), and all elements in the array are then re-added to the new array.

NOTE: Resizing involves recalculating the initial indexes for all elements all over again! Remember our formula for calculating initial index is:

$initIndex = element.hashCode() % array.length$.

If the array length as doubled, you can best be assured the initIndex will be changed.

You can convince yourself that adding (which is the only way to increase LF, and therefore trigger resizing) is in the worst case $O(n^{2})$, as you will need to potentially recalculate locations of all elements and then go through the process of trying to add one element.

One edge case I did see when I had to implement a HashMap for a homework assignment (where the resolution strategy was linear probing) was that it is indeed possible to have every array index be filled, yet have the LF be within the bounds? How is this possible?

One nuance of linear probing involves our removal process. When we remove an element, we don't actually remove it from the hash table. What we do is we mark it as removed, and then move on. If we add to the same index later on and we find a removed element, we overwrite it.

Removing an element decreases size by one, and decreases LF appropriately. But what you can do is you can have a mixture of removed elements and regular elements in your array, such that no index is TRULY empty, and still have the LF be less than the bound you've established. I myself didn't even think it was possible, but lo and behold, after writing the diagrams down on paper, I realized this was an edge case I had not foreseen.


SHORT ANSWER (THANKS FOR READING)

It's not really possible with a probing strategy to exceed LF = 1 given that you'll have only one element in every spot at the absolute maximum.

If you implement the Hash Table at any point, you'll probably be told to institute some bound where if LF = .75 or greater, you need to trigger resizing. This necessarily implies that some array indices will be empty or have removed elements. With this in mind, it is clear to see that unless you implement the Hash Table incorrectly, you'll never really reach an LF of 1.

The reason we do this is to keep the Hash Table's super-fast retrieval/search times (usually O(1) in the best case). Having an LF that continuously increases decreases the effectiveness of searching processes, and forces us to increase our search time to an O(n) process.

Hopefully this helps! Sorry for the long answer. If you want, I can cut out portions of it deemed unnecessary to the answer, but I wanted to make sure Hash Tables were explained (somewhat) well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.