Implement Hash without STL in C++ and Java Language:

A hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values.
Hash table uses a hash function to compute an index searching into an array of buckets or slots.

[problem]
Store the given N key and data pairs into a hash table, then print each data matching to Q key inputs. * Key : Max 64 chars * Data : Max 128 chars

[Input]
The first input line contains the number of test cases, T.
The next line contains the number of keys and data pairs, N (1<= N <= 4096).
For the following N lines, key and data will be given.
Then the number of keys to search, Q (1 <= Q <= 4096) is given.

[Output]
For each given test case, print the data matching to the given keys.




INPUT                                                    OUTPUT
===========================         =============                     
2 // Number of Test cases T #1
8 // Number of input data N Charm
Attract Charm //key data Amaze
Gather Collect not find
Fundamental Essential #2
Abundant Plentiful not find
Achieve Accomplish Stand
Assign Allocate                                        Flaw
Surprise Amaze Tremendous
Assess Estimate                                         not find
3 // Number of data to search Q
Attract
Surprise
education
10
Bear
Stand
Famous
Noted
Characteristic
Attribute
Decrease
Diminish
Defect
Flaw
Depict
Describe
Eager
Avid
Flourish
Thrive
Huge
Tremendous
Important
Crucial
5
treasure
Bear
Defect
Huge
hydrogen


JAVA SOURCE:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Hashtable;
import java.util.Scanner;

class Hash
{
   final static int MAX_TABLE = 4096;
    static private final String INPUT = System.getProperty("user.dir") + "\\src\\data\\hashMap.txt";

    public static void main(String[] args) {

    FileInputStream instream = null;
    try {
        instream = new FileInputStream(INPUT);
        System.setIn(instream);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }

    Scanner sc =  new Scanner(System.in);
    int T = sc.nextInt();
    for(int test_case = 1;test_case <=T;test_case++)
    {
        HashMap hm = new HashMap(MAX_TABLE);
        int N = sc.nextInt();

        for(int i=0;i<N;i++)
        {
            String key = sc.next();
            String data = sc.next();
            hm.add(key, data);
        }

        System.out.printf("#%d\n",test_case);
        int Q = sc.nextInt();
        for(int i=0;i<Q;i++)
        {
            String key = sc.next();
            String data = hm.find(key);

            if(data != null)
            {
                System.out.printf("%s\n",data);
            }
            else
            {
                System.out.printf("not find\n");
            }
        }

    }
    sc.close();
}

 }

class HashMap
{
class HashTable
{
    String key;
    String data;
}

int capacity;
HashTable ht[];

public HashMap(int capacity) {
    this.capacity = capacity;
    ht = new HashTable[capacity];

    for(int i=0;i<capacity;i++)
    {
        ht[i] = new HashTable();
    }
}

private int hashCreateTableRow(String str)
{
    int hash = 5381;

    for(int i=0;i<str.length();i++)
    {
        int c = (int)str.charAt(i);
        hash = ((hash<<5)+ hash) + c;
    }

    if(hash<0) hash *=-1;
    return hash % capacity;
}

public String find(String key)
{
    int h = hashCreateTableRow(key);
    int cnt = capacity;

    while(ht[h].key != null && (--cnt) != 0)
    {
        if(isEquals(key,ht[h].key))
        {
            return ht[h].data;
        }
        h = (h+1) % capacity;
    }

    return null;
}

public boolean add(String key,String data)
{
    int h = hashCreateTableRow(key);
    while(ht[h].key != null)
    {
        if(isEquals(key,ht[h].key))
        {
            return false;
        }
        h = (h+1) % capacity;
    }
    ht[h].key = key;
    ht[h].data = data;

    return true;
}

public static boolean isEquals(String input1,String input2)
{
    if(input1 == input2) return true;

    int len1 = input1.length();
    int len2 = input2.length();

    if (len1 != len2)
    {
        return false;
    }


    for (int i = 0, j = 0; i < len1; i++, j++)
    {
        if (input1.charAt(i) != input2.charAt(j))
        {
            return false;
        }
    }

    return true;
}
}

C++ Source :

#include<iostream>
#include<stdio.h>
#include <string.h>
#include <memory.h>

using namespace std;
#define MAX_KEY 64
#define MAX_DATA 128
#define MAX_TABLE 4096

typedef struct HashMap
{
  char key[MAX_KEY + 1];
  char data[MAX_DATA + 1];
};

HashMap tb[MAX_TABLE];

unsigned long hashCreateTableRow(const char *str);
int find(const char *key, char *data);
int add(const char *key, char *data);

int main(int argc, char* argv[])
{
int T, N, Q;

freopen("CreateHashMap.txt", "r", stdin);
cin >> T;

for (int test_case = 1; test_case <= T; test_case++)
{
    memset(tb, 0, sizeof(tb));
    cin >> N;
    char k[MAX_KEY + 1];
    char d[MAX_DATA + 1];

    for (int i = 0; i < N; i++)
    {
        cin >> k >> d;
        add(k, d);
    }

    cout << "#" << test_case << " " << endl;

    cin >> Q;

    for (int i = 0; i < Q; i++)
    {
        char k[MAX_KEY + 1];
        char d[MAX_DATA + 1];

        cin >> k;
        if (find(k, d))
        {
            cout << d << endl;
        }
        else
        {
            cout << "not find" << endl;
        }
    }
}
return 0;
}


unsigned long hashCreateTableRow(const char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
{
    hash = (((hash << 5) + hash) + c) % MAX_TABLE;
}

return hash % MAX_TABLE;
}

int find(const char *key, char *data)
{
unsigned long h = hashCreateTableRow(key);
int cnt = MAX_TABLE;
int step = 1;

while (tb[h].key[0] != 0 && cnt--)
{
    if (strcmp(tb[h].key, key) == 0)
    {
        strcpy(data, tb[h].data);
        return 1;
    }
    h = (h + 1) % MAX_TABLE;
}
return 0;
}

int add(const char *key, char *data)
{
unsigned long h = hashCreateTableRow(key);
int step = 1;
int i = 0;

while (tb[h].key[0] != 0)
{
    if (strcmp(tb[h].key, key) == 0)
    {
        return 0;
    }

    h = (h + 1) % MAX_TABLE;
}
strcpy(tb[h].key, key);
strcpy(tb[h].data, data);
return 1;
}