C++ Tutorials

C++ Tutorials

These data structures are getting complicated enough that they’re fairly hard to read. We need to think about what components we need to represent the hash table.

The main component we need is a way of representing a bucket. So here’s our picture of our hash table. What we want is a list. This is going to be the list where each element in the list is a bucket. And what a bucket is is a list itself where each element in that list is a key and a value. In our case, the key is the word, the value is the list of URLs.

So the structure that corresponds to that most closely is this one where we have a list, each inner list here. So this corresponds to a bucket, and then within the bucket a word and a list of URLs is 1 entry.

This corresponds to what the entries were in our previous index, but now because we want to make it a hash table, we’re going to collect them in buckets. So a list of those entries and each element in the outer list corresponds to 1 bucket.

I hope everyone understands the main idea behind the hash table now. Our goal is to map a keyword and the number of buckets using a hashstring function to a particular bucket, and that bucket will contain all of the keywords that map to that location.

So now what we’re going to do is try to actually write the code to do this. We’re going to start from our index that we wrote for the previous unit but try to figure out how to implement that with a hash table instead.

The first question is, how is this going to change our data structure? This was what we had before. If you remember, we had our index was a list of keywords.

We had a list of entries, and each entry was a pair, which was a keyword, and the second element of the pair was a list of the URLs where that word appears. And we would have each word in the index as its own entry with its own list of URLs.

So this was the data structure that we used last class. Now we want to change things to implement a hash table. I want you to think about what data structure I’ll use, and we’ll make that a quiz to decide a good data structure to use to implement the hash table.

The question is, which of these data structures would make most sense to implement the hash table index? The first choice is a list where the elements in the list are a list where the first element is a word and the second element is a list of URLs where that word appears.

The second choice is a list where each element in the list is a list itself where the first element is a word and the second element is a list of lists where each element in that list is a list of URLs.

The third choice is a list where each element is a list where the element lists themselves contain lists where the element lists of the element lists are a list of a word followed by a list of all the URLs where that word appears.

So we have 3 nested lists for choice 3. For choice 4 we have a list where each element of the list is a list where within the element list there’s another list which is a list of words followed by a list of URLs.

And for the final choice we also have 3 nested lists where each element list is a list where the elements of that list are lists that are a word followed by a list where each element in that list is a list of URLs. So which one of these would be the best structure to use to implement a hash table?

Hash table c++ stl

#include <iostream>
#include <list>

using namespace std;

class HashTable{
private:
  list<int> *table;
  int total_elements;

  // Hash function to calculate hash for a value:
  int getHash(int key){
    return key % total_elements;
  }

public:
  // Constructor to create a hash table with 'n' indices:
  HashTable(int n){
    total_elements = n;
    table = new list<int>[total_elements];
  }

  // Insert data in the hash table:
  void insertElement(int key){
    table[getHash(key)].push_back(key);
  }

  // Remove data from the hash table:
  void removeElement(int key){
    int x = getHash(key);

    list<int>::iterator i; 
    for (i = table[x].begin(); i != table[x].end(); i++) { 
      // Check if the iterator points to the required item:
      if (*i == key) 
        break;
    }

    // If the item was found in the list, then delete it:
    if (i != table[x].end()) 
      table[x].erase(i);
  }

  void printAll(){
    // Traverse each index:
    for(int i = 0; i < total_elements; i++){
      cout << "Index " << i << ": ";
      // Traverse the list at current index:
      for(int j : table[i])
        cout << j << " => ";

      cout << endl;
    }
  }
};

int main() {
  // Create a hash table with 3 indices:
  HashTable ht(3);

  // Declare the data to be stored in the hash table:
  int arr[] = {2, 4, 6, 8, 10};

  // Insert the whole data into the hash table:
  for(int i = 0; i < 5; i++)
    ht.insertElement(arr[i]);

  cout << "..:: Hash Table ::.." << endl;
  ht.printAll();
  
  ht.removeElement(4);
  cout << endl << "..:: After deleting 4 ::.." << endl;
  ht.printAll();

  return 0;
}

So I hope everyone understands the main idea behind the hash table now. Our goal is to map a keyword and a number of buckets. Using our hash-string function to a particular bucket and that bucket will contain all of the keywords that map to that location.

So now what we’re going to do is try to actually write the code to do this. We’re going to start from our index that we wrote for the previous unit, but try to figure out how to implement that with a hash table instead.

So the first question is, how is this going to change our data structure? So this was what we had before, if you remember we had our index was a list of keywords, we had a list of entries, and each entry was a pair, which was a keyword.

And the second element of the pair was the list of the URLs where that word appears, and we would have each word in the index as its own entry with its own list of URLs. So this was the data structure that we used last class.

Now we want to change things to implement a hash table. So, I want you to think about what data structure we’ll use and we’ll make that a quiz to decide a good data structure to use to implement the hash table.

So the question is which of these data structures would make most sense to implement the hash table index? The first choice is a list. Where the elements in the list are.

A list where the first element is a word and the second element is a list of URLs where that word appears. The second choice is a list where each element in a list is the list itself where the first element is a word and the second element is a list of lists where each element in that list is a list of URLs.

So, the third choice is a list. Where each element is a list. Where the element lists themselves contain lists. Where the element lists of the element list are a list of the word, all by a list of all the URLs for that word. So, we have three nested lists for choice three. For choice four, we have a list where each element in the list is a list.

Where within the element list, there is another list, which is a list of words, followed by a list of URLs. And for the final choice, we also have three nest of lists, where each element is a list, where the elements of that list are a list, that is word followed by a list. Where each element in that list is a list of URLs. So which one of these would be the best structure to implement a hash table?

Hashing program in c++

hash table is a data structure which is used to store key-value pairs. Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched.

// CPP program to implement hashing with chaining
#include<iostream>
#include <list>
using namespace std;
 
class Hash
{
    int BUCKET;    // No. of buckets
 
    // Pointer to an array containing buckets
    list<int> *table;
public:
    Hash(int V);  // Constructor
 
    // inserts a key into hash table
    void insertItem(int x);
 
    // deletes a key from hash table
    void deleteItem(int key);
 
    // hash function to map values to key
    int hashFunction(int x) {
        return (x % BUCKET);
    }
 
    void displayHash();
};
 
Hash::Hash(int b)
{
    this->BUCKET = b;
    table = new list<int>[BUCKET];
}
 
void Hash::insertItem(int key)
{
    int index = hashFunction(key);
    table[index].push_back(key); 
}
 
void Hash::deleteItem(int key)
{
  // get the hash index of key
  int index = hashFunction(key);
 
  // find the key in (inex)th list
  list <int> :: iterator i;
  for (i = table[index].begin();
           i != table[index].end(); i++) {
    if (*i == key)
      break;
  }
 
  // if key is found in hash table, remove it
  if (i != table[index].end())
    table[index].erase(i);
}
 
// function to display hash table
void Hash::displayHash() {
  for (int i = 0; i < BUCKET; i++) {
    cout << i;
    for (auto x : table[i])
      cout << " --> " << x;
    cout << endl;
  }
}
 
// Driver program 
int main()
{
  // array that contains keys to be mapped
  int a[] = {15, 11, 27, 8, 12};
  int n = sizeof(a)/sizeof(a[0]);
 
  // insert the keys into the hash table
  Hash h(7);   // 7 is count of buckets in
               // hash table
  for (int i = 0; i < n; i++) 
    h.insertItem(a[i]);  
 
  // delete 12 from hash table
  h.deleteItem(12);
 
  // display the Hash table
  h.displayHash();
 
  return 0;
}
Output:
0
1 --> 15 --> 8
2
3
4 --> 11
5
6 --> 27

Hash table c++ associative array

We’ll be looking at how to Find the element that appears once in an array where every other element appears twice. We’ll be Given an array of integers.

All numbers occur twice except one number which occurs once. Find the number in O(n) time & constant extra space. Let’s look at an example if the input array is this… Our output should be 7 because 7 appears once in this array First, we’ll look at a simple solution.

A simple solution is to check every element if it appears once or not. Once an an element with single occurrence is found, return it. Time complexity of this solution is O(n^2).

A better solution is to use hashing. Traverse all elements and put them in a hash table. Element is used as key and count of occurrences is used as value. Traverse the array again and print the element with count 1 in hash table.

This solution works in O(n) time, but requires extra space. Solution using XOR. The best solution is to use XOR. XOR of all array elements gives us the number with single occurrence. The idea is based on following two facts. First, XOR of a number with itself is 0.

Second, XOR of a number with 0 is number itself. Let’s try to implement this on the above example. Here we are performing XOR on all array elements. Since XOR is associative and commutative, above expression can be written as this. The XOR of a number with itself is 0, therefore all of this is zero.

We are left with 7 XOR 0 which is equal to 7, according to our second property. Let’s look at the c++ code. It is a very simple code, we are just running a loop to traverse through our given array and XORing all the elements.

At last we will return the result. Time complexity of this solution is O(n) and it requires O(1) extra space which is constant space.

Linear probing hash table c++

Hash Tables
• Suboperations
– Compute h(k) should be _ – Array access of table[h(k)] =
• In a hash table using chaining, what is the
expected efficiency of each operation
– Find = _

– Insert =
– Remove = _

The second disadvantage is in construction, particularly contention in the construction process. What we might have is 2 different items, each of which wants to place 1 item into the hash table.

Let’s say both of these items decide that they have the same hash function for their particular item, and so they both want to add an item to hash table bucket number 12, for instance. These 2 items want to simultaneously manipulate the link list in the same bucket.

To do that, they’re going to have to serialize and synchronize. Only 1 of them can update the bucket at any given time, and the other must wait its turn. So any serialization like this within a parallel algorithm is definitely undesirable, as well. So the conclusion here is that chaining is a sub-optimal strategy if were dealing with parallel hash tables. So we’re going to turn to a different method.

A hash table with linear probing requires you

  • Initiate a linear search starting at the hashed-to location for an empty slot in which to store your key+value.
  • If the slot encountered is empty, store your key+value; you’re done.
  • Otherwise, if they keys match, replace the value; you’re done.
  • Otherwise, move to the next slot, hunting for any empty or key-matching slot, at which point (2) or (3) transpires.
  • To prevent overrun, the loop doing all of this wraps modulo the table size.
  • If you run all the way back to the original hashed-to location and still have no empty slot or matching-key overwrite, your table is completely populated (100% load) and you cannot insert more key+value pairs.

That’s it. In practice it looks something like this:

bool hashEntry(string key, string value, entry HashTable[], int p)
{
    bool inserted = false;
    int hval = Hash(key, p);

    for (int i = 0; !inserted && i < p; i++)
    {
        if (HashTable[(hval + i) % p].key_de.empty())
        {
            HashTable[(hval + i) % p].key_de = key;
        }

        if (HashTable[(hval + i) % p].key_de == key)
        {
            HashTable[(hval + i) % p].val_en = value;
            inserted = true;
        }
    }

    return inserted;
}

Quadratic probing hash table c++

Quadratic Probing
– h(k,i) = (h(k)+i^2) mod m
– Check location h(k)+12
, h(k)+22
, h(k)+32

Example

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;
/*
 * Node Type Declaration
 */
enum EntryType {Legitimate, Empty, Deleted};
/*
 * Node Declaration
 */
struct HashNode
{
    int element;
    enum EntryType info;
};
/*
 * Table Declaration
 */
struct HashTable
{
    int size;
    HashNode *table;
};
/*
 * Returns whether n is prime or not
 */
bool isPrime (int n)
{
    if (n == 2 || n == 3)
        return true;
    if (n == 1 || n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}
/*
 * Finding next prime size of the table
 */
int nextPrime(int n)
{
    if (n <= 0)
        n == 3;
    if (n % 2 == 0)
        n++;
    for (; !isPrime( n ); n += 2);
    return n;
}
/*
 * Function To Generate Hash
 */
int HashFunc(int key, int size)
{
    return key % size;
}
/*
 * Function to Initialize Table
 */
HashTable *initializeTable(int size)
{
    HashTable *htable;
    if (size < MIN_TABLE_SIZE)
    {
        cout<<"Table Size Too Small"<<endl;
        return NULL;
    }
    htable = new HashTable;
    if (htable == NULL)
    {
        cout<<"Out of Space"<<endl;
        return NULL;
    }
    htable->size = nextPrime(size);
    htable->table = new HashNode [htable->size];
    if (htable->table == NULL)
    {
        cout<<"Table Size Too Small"<<endl;
        return NULL;
    }
    for (int i = 0; i < htable->size; i++)
    {
        htable->table[i].info = Empty;
        htable->table[i].element = NULL;
    }
    return htable;
}
/*
 * Function to Find Element at a key
 */
int Find(int key, HashTable *htable)
{
    int pos = HashFunc(key, htable->size);
    int collisions = 0;
    while (htable->table[pos].info != Empty &&
           htable->table[pos].element != key)
    {
        pos = pos + 2 * ++collisions -1;
        if (pos >= htable->size)
            pos = pos - htable->size;
    }
    return pos;
}
/*
 * Function to Insert Element into a key
 */
void Insert(int key, HashTable *htable)
{
    int pos = Find(key, htable);
    if (htable->table[pos].info != Legitimate)
    {
        htable->table[pos].info = Legitimate;
        htable->table[pos].element = key;
    }
}
/*
 * Function to Rehash the Table
 */
HashTable *Rehash(HashTable *htable)
{
    int size = htable->size;
    HashNode *table = htable->table;
    htable = initializeTable(2 * size);
    for (int i = 0; i < size; i++)
    {
        if (table[i].info == Legitimate)
            Insert(table[i].element, htable);
    }
    free(table);
    return htable;
}
/*
 * Function to Retrieve Hash Table
 */
void Retrieve(HashTable *htable)
{
    for (int i = 0; i < htable->size; i++)
    {
        int value = htable->table[i].element;
        if (!value)
            cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
        else
            cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
    }

}
/*
 * Main Contains Menu
 */
int main()
{
    int value, size, pos, i = 1;
    int choice;
    HashTable *htable;
    while(1)
    {
        cout<<"\n----------------------"<<endl;
        cout<<"Operations on Quadratic Probing"<<endl;
        cout<<"\n----------------------"<<endl;
        cout<<"1.Initialize size of the table"<<endl;
        cout<<"2.Insert element into the table"<<endl;
        cout<<"3.Display Hash Table"<<endl;
        cout<<"4.Rehash The Table"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter size of the Hash Table: ";
            cin>>size;
            htable = initializeTable(size);
            cout<<"Size of Hash Table: "<<nextPrime(size);
            break;
        case 2:
            if (i > htable->size)
            {
                cout<<"Table is Full, Rehash the table"<<endl;
                continue;
            }
        	cout<<"Enter element to be inserted: ";
        	cin>>value;
            Insert(value, htable);
            i++;
            break;
        case 3:
            Retrieve(htable);
            break;
        case 4:
            htable = Rehash(htable);
            break;
        case 5:
            exit(1);
        default:
           cout<<"\nEnter correct option\n";
       }
    }
    return 0;
}