Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Hash table. Collision resolution by chaining (closed addressing)

Chaining is a possible way to resolve collisions. Each slot of the array contains a link to a singly-linked list containing key-value pairs with the same hash. New key-value pairs are added to the end of the list. Lookup algorithm searches through the list to find matching key. Initially table slots contain nulls. List is being created, when value with the certain hash is added for the first time.

Chaining illustration

Hash table: chaining illustration

Complexity analysis

Assuming, that hash function distributes hash codes uniformly and table allows dynamic resizing, amortized complexity of insertion, removal and lookup operations is constant. Actual time, taken by those operations linearly depends on table's load factor.

Note. Even substantially overloaded hash table, based on chaining, shows well performance. Assume hash table with 1000 slots storing 100000 items (load factor is 100). It requires a bit more memory (size of the table), than a singly-linked list, but all basic operations will be done about 1000 times faster on average. Draw attention, that computational complexity of both singly-linked list and constant-sized hash table is O(n).

Chaining vs. open addressing

See open addressing vs. chaining.

Code snippets

Code given below implements chaining with list heads. It means, that hash table entries contain first element of a linked-list, instead of storing pointer to it.

Java implementation

public class LinkedHashEntry {

      private int key;

      private int value;

      private LinkedHashEntry next;

 

      LinkedHashEntry(int key, int value) {

            this.key = key;

            this.value = value;

            this.next = null;

      }

 

      public int getValue() {

            return value;

      }

 

      public void setValue(int value) {

            this.value = value;

      }

 

      public int getKey() {

            return key;

      }

 

      public LinkedHashEntry getNext() {

            return next;

      }

 

      public void setNext(LinkedHashEntry next) {

            this.next = next;

      }

}

 

public class HashMap {

      private final static int TABLE_SIZE = 128;

 

      LinkedHashEntry[] table;

 

      HashMap() {

            table = new LinkedHashEntry[TABLE_SIZE];

            for (int i = 0; i < TABLE_SIZE; i++)

                  table[i] = null;

      }

 

      public int get(int key) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] == null)

                  return -1;

            else {

                  LinkedHashEntry entry = table[hash];

                  while (entry != null && entry.getKey() != key)

                        entry = entry.getNext();

                  if (entry == null)

                        return -1;

                  else

                        return entry.getValue();

            }

      }

 

      public void put(int key, int value) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] == null)

                  table[hash] = new LinkedHashEntry(key, value);

            else {

                  LinkedHashEntry entry = table[hash];

                  while (entry.getNext() != null && entry.getKey() != key)

                        entry = entry.getNext();

                  if (entry.getKey() == key)

                        entry.setValue(value);

                  else

                        entry.setNext(new LinkedHashEntry(key, value));

            }

      }

 

      public void remove(int key) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] != null) {

                  LinkedHashEntry prevEntry = null;

                  LinkedHashEntry entry = table[hash];

                  while (entry.getNext() != null && entry.getKey() != key) {

                        prevEntry = entry;

                        entry = entry.getNext();

                  }

                  if (entry.getKey() == key) {

                        if (prevEntry == null)

                             table[hash] = entry.getNext();

                        else

                             prevEntry.setNext(entry.getNext());

                  }

            }

      }

}

 

C++ implementation

class LinkedHashEntry {

private:

      int key;

      int value;

      LinkedHashEntry *next;

public:

      LinkedHashEntry(int key, int value) {

            this->key = key;

            this->value = value;

            this->next = NULL;

      }

 

      int getKey() {

            return key;

      }

 

      int getValue() {

            return value;

      }

 

      void setValue(int value) {

            this->value = value;

      }

 

      LinkedHashEntry *getNext() {

            return next;

      }

 

      void setNext(LinkedHashEntry *next) {

            this->next = next;

      }

};

 

const int TABLE_SIZE = 128;

 

class HashMap {

private:

      LinkedHashEntry **table;

public:

      HashMap() {

            table = new LinkedHashEntry*[TABLE_SIZE];

            for (int i = 0; i < TABLE_SIZE; i++)

                  table[i] = NULL;

      }

 

      int get(int key) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] == NULL)

                  return -1;

            else {

                  LinkedHashEntry *entry = table[hash];

                  while (entry != NULL && entry->getKey() != key)

                        entry = entry->getNext();

                  if (entry == NULL)

                        return -1;

                  else

                        return entry->getValue();

            }

      }

 

      void put(int key, int value) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] == NULL)

                  table[hash] = new LinkedHashEntry(key, value);

            else {

                  LinkedHashEntry *entry = table[hash];

                  while (entry->getNext() != NULL)

                        entry = entry->getNext();

                  if (entry->getKey() == key)

                        entry->setValue(value);

                  else

                        entry->setNext(new LinkedHashEntry(key, value));

            }

      }

 

      void remove(int key) {

            int hash = (key % TABLE_SIZE);

            if (table[hash] != NULL) {

                  LinkedHashEntry *prevEntry = NULL;

                  LinkedHashEntry *entry = table[hash];

                  while (entry->getNext() != NULL && entry->getKey() != key) {

                        prevEntry = entry;

                        entry = entry->getNext();

                  }

                  if (entry->getKey() == key) {

                        if (prevEntry == NULL) {

                             LinkedHashEntry *nextEntry = entry->getNext();

                             delete entry;

                             table[hash] = nextEntry;

                        } else {

                             LinkedHashEntry *next = entry->getNext();

                              delete entry;

                             prevEntry->setNext(next);

                        }

                  }

            }

      }

 

      ~HashMap() {

            for (int i = 0; i < TABLE_SIZE; i++)

                  if (table[i] != NULL) {

                        LinkedHashEntry *prevEntry = NULL;

                        LinkedHashEntry *entry = table[i];

                        while (entry != NULL) {

                             prevEntry = entry;

                             entry = entry->getNext();

                             delete prevEntry;

                        }

                  }

            delete[] table;

      }

};


Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: