Hash Functions – Intro

The idea of a hash function is to map from the domain of the key (which can be quite large), into the range of the the (much smaller) storage array.

The key may be a number, but could also be a string:

For example, what if we want to map from a country to a its capital:

Key	Value
Italy	Rome
France	Paris
England	London
Australia	Canberra
Switzerland	Berne

Hash Function Steps:

Convert Text to a Unique Number: We calculate a unique number by assigning each letter in the word a value based on its position. Using a Polynomial Rolling Hash method:
hash = x₁*A⁰ + x₂*Aⁱ + x₃*A² … xₙ*Aⁿ⁻ⁱ
For example, the word “CAB”:

C: 5⋅31⁰=5
A: 2⋅31¹=62
B: 3⋅31²=2883

Final hash for “CAB”: 5 + 62 + 2883 = 2950.

2. Apply a Modulus for Hash Table Indexing: The hash function should distribute values uniformly. We typically use:
h(K) = key mod M
Here,
k is the key value, and
M is the size of the hash table.

So in the case above:

2950%250 = 200

Code to map from string to index: github

#include <iostream>
#include <string>
using namespace std;

const int PRIME_CONST = 31;
const int HASH_TABLE_SIZE = 250;

long long hashFunction(const string& key) {
    long long hashCode = 0;
    long long power = 1; // Efficiently handle powers of PRIME_CONST
    for (char ch : key) {
        hashCode += ch * power;
        power *= PRIME_CONST;
    }
    return hashCode;
}

int main() {
    string key;
    cout << "Enter word (or 'quit' to exit): ";
    while (getline(cin, key) && key != "quit") {
        long long hashValue = hashFunction(key);
        int index = hashValue % HASH_TABLE_SIZE;
        cout << "Word \"" << key << "\" maps to index: " << index << endl;
        cout << "Enter word (or 'quit' to exit): ";
    }
    return 0;
}

Code to implement simple hash table: github

#include <iostream>
#include <string>
#include <utility>
using namespace std;

class HashTable {
    static const int PRIME_CONST = 31;
    static const int ARR_SIZE = 3001;
    pair<string, string> table[ARR_SIZE];

public:
    HashTable() {
        for (auto& entry : table) {
            entry = {"", ""};
        }
    }

    void put(const string& key, const string& value) {
        int index = hashFunc(key);
        if (table[index].first.empty() || table[index].first == key) {
            table[index] = {key, value};
        } else {
            // Linear probing for collision resolution
            int originalIndex = index;
            do {
                index = (index + 1) % ARR_SIZE;
            } while (!table[index].first.empty() && table[index].first != key && index != originalIndex);

            if (index == originalIndex) {
                cout << "Hash table is full!" << endl;
                return;
            }
            table[index] = {key, value};
        }
    }

    string get(const string& key) {
        int index = hashFunc(key);
        int originalIndex = index;
        while (!table[index].first.empty()) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % ARR_SIZE;
            if (index == originalIndex) break;
        }
        cout << "Not found." << endl;
        return "";
    }

    static int hashFunc(const string& key) {
        long long sum = 0;
        long long power = 1;
        for (char ch : key) {
            sum = (sum + (ch * power) % ARR_SIZE) % ARR_SIZE;
            power = (power * PRIME_CONST) % ARR_SIZE;
        }
        return static_cast<int>(sum);
    }

    void printAll() const {
        for (const auto& entry : table) {
            if (!entry.first.empty()) {
                cout << entry.first << " => " << entry.second << endl;
            }
        }
        cout << endl;
    }
};

int main() {
    HashTable hTable;
    string cmd, key, value;
    cout << "1. Add, 2. Lookup, 3. List, 4. Exit: ";
    while (getline(cin, cmd) && cmd != "4") {
        if (cmd == "1") {
            cout << "Enter key: ";
            getline(cin, key);
            cout << "Enter value: ";
            getline(cin, value);
            hTable.put(key, value);
        } else if (cmd == "2") {
            cout << "Enter key to find: ";
            getline(cin, key);
            value = hTable.get(key);
            if (!value.empty()) {
                cout << key << " => " << value << endl;
            }
        } else if (cmd == "3") {
            hTable.printAll();
        } else {
            cout << "Invalid command." << endl;
        }
        cout << "1. Add, 2. Lookup, 3. List, 4. Exit: ";
    }
    return 0;
}

A list of countries and capitals:

Afghanistan,Kabul
Albania,Tirana
Algeria,Algiers
Andorra,Andorra la Vella
Angola,Luanda
Antigua and Barbuda,St. John’s
Argentina,Buenos Aires
Armenia,Yerevan
Australia,Canberra
Austria,Vienna
Azerbaijan,Baku
Bahamas,Nassau
Bahrain,Manama
Bangladesh,Dhaka
Barbados,Bridgetown
Belarus,Minsk
Belgium,Brussels
Belize,Belmopan
Benin,Porto-Novo
Bhutan,Thimphu
Bolivia,Sucre
Bosnia and Herzegovina,Sarajevo
Botswana,Gaborone
Brazil,Brasilia
Brunei,Bandar Seri Begawan
Bulgaria,Sofia
Burkina Faso,Ouagadougou
Burundi,Gitega
Cabo Verde,Praia
Cambodia,Phnom Penh
Cameroon,Yaounde
Canada,Ottawa
Central African Republic,Bangui
Chad,N’Djamena
Chile,Santiago
China,Beijing
Colombia,Bogota
Comoros,Moroni
Congo,Brazzaville
Costa Rica,San Jose
Croatia,Zagreb
Cuba,Havana
Cyprus,Nicosia
Czech Republic,Prague
Denmark,Copenhagen
Djibouti,Djibouti
Dominica,Roseau
Dominican Republic,Santo Domingo
Ecuador,Quito
Egypt,Cairo
El Salvador,San Salvador
Equatorial Guinea,Malabo
Eritrea,Asmara
Estonia,Tallinn
Eswatini,Mbabane
Ethiopia,Addis Ababa
Fiji,Suva
Finland,Helsinki
France,Paris
Gabon,Libreville
Gambia,Banjul
Georgia,Tbilisi
Germany,Berlin
Ghana,Accra
Greece,Athens
Grenada,St. George’s
Guatemala,Guatemala City
Guinea,Conakry
Guinea-Bissau,Bissau
Guyana,Georgetown
Haiti,Port-au-Prince
Honduras,Tegucigalpa
Hungary,Budapest
Iceland,Reykjavik
India,New Delhi
Indonesia,Jakarta
Iran,Tehran
Iraq,Baghdad
Ireland,Dublin
Israel,Jerusalem
Italy,Rome
Jamaica,Kingston
Japan,Tokyo
Jordan,Amman
Kazakhstan,Astana
Kenya,Nairobi
Kiribati,South Tarawa
Korea,North,Pyongyang
Korea,South,Seoul
Kosovo,Pristina
Kuwait,Kuwait City
Kyrgyzstan,Bishkek
Laos,Vientiane
Latvia,Riga
Lebanon,Beirut
Lesotho,Maseru
Liberia,Monrovia
Libya,Tripoli
Liechtenstein,Vaduz
Lithuania,Vilnius
Luxembourg,Luxembourg
Madagascar,Antananarivo
Malawi,Lilongwe
Malaysia,Kuala Lumpur
Maldives,Male
Mali,Bamako
Malta,Valletta
Marshall Islands,Majuro
Mauritania,Nouakchott
Mauritius,Port Louis
Mexico,Mexico City
Micronesia,Palikir
Moldova,Chisinau
Monaco,Monaco
Mongolia,Ulaanbaatar
Montenegro,Podgorica
Morocco,Rabat
Mozambique,Maputo
Myanmar,Naypyidaw
Namibia,Windhoek
Nauru,Yaren District
Nepal,Kathmandu
Netherlands,Amsterdam
New Zealand,Wellington
Nicaragua,Managua
Niger,Niamey
Nigeria,Abuja
North Macedonia,Skopje
Norway,Oslo
Oman,Muscat
Pakistan,Islamabad
Palau,Ngerulmud
Panama,Panama City
Papua New Guinea,Port Moresby
Paraguay,Asuncion
Peru,Lima
Philippines,Manila
Poland,Warsaw
Portugal,Lisbon
Qatar,Doha
Romania,Bucharest
Russia,Moscow
Rwanda,Kigali
Saint Kitts and Nevis,Basseterre
Saint Lucia,Castries
Saint Vincent and the Grenadines,Kingstown
Samoa,Apia
San Marino,San Marino
Sao Tome and Principe,Sao Tome
Saudi Arabia,Riyadh
Senegal,Dakar
Serbia,Belgrade
Seychelles,Victoria
Sierra Leone,Freetown
Singapore,Singapore
Slovakia,Bratislava
Slovenia,Ljubljana
Solomon Islands,Honiara
Somalia,Mogadishu
South Africa,Pretoria
South Sudan,Juba
Spain,Madrid
Sri Lanka,Sri Jayawardenepura Kotte
Sudan,Khartoum
Suriname,Paramaribo
Sweden,Stockholm
Switzerland,Bern
Syria,Damascus
Taiwan,Taipei
Tajikistan,Dushanbe
Tanzania,Dodoma
Thailand,Bangkok
Timor-Leste,Dili
Togo,Lome
Tonga,Nuku’alofa
Trinidad and Tobago,Port of Spain
Tunisia,Tunis
Turkey,Ankara
Turkmenistan,Ashgabat
Tuvalu,Funafuti
Uganda,Kampala
Ukraine,Kyiv
United Arab Emirates,Abu Dhabi
United Kingdom,London
United States,Washington D.C.
Uruguay,Montevideo
Uzbekistan,Tashkent
Vanuatu,Port Vila
Vatican City,Vatican City
Venezuela,Caracas
Vietnam,Hanoi
Yemen,Sana’a
Zambia,Lusaka
Zimbabwe,Harare