Difference between HashMap and HashTable purely in Data Structures

Question

What is the difference between HashTable and HashMap purely in context of data structures (and not in Java or any other language)?

I have seen people using these terms interchangeably for the same concept. Does it have no difference at all purely in context of data structures?

Carmon

There's no standard HashTable or HashMap type in C. The two terms are usually used interchangeably. – Styracaceous

I am aware of it that there is no such standard HashTable or HashMap in C. All I meant was when programming its concept in C is there any difference between both. – Carmon

then this has nothing to do with C. C has no notion of "HashMap" or "HashTable". – Styracaceous

The reason I mentioned C was that the question may not be mistaken as another question asking its difference in java. – Carmon

As pointed out there are no "HashMap"/"HashTable" in iso standard C. There is a hashmap in the boost lib for C++ though. Also, this question is a Duplicate of #3578583 – Kantian

Can't see how the lnk is convincing about its similarity! I don't know how is it duplicate of the link mentioned. – Carmon

Answer 1

In Computing Science terminology, a map is an associative container mapping from a key to a value. In other words, you can do operations like "for key K remember value V" and later "for key K get the value". A map can be implemented in many ways - for example, with a (optionally balanced) binary tree, or a hash table, or even a contiguous array of structs storing the key/value.

A hash table is a structure for storing arbitrary data, and that data does not necessarily consist of a separate key and value. For example, I could have a hash table containing the values { 1, 10, 33, 97 }, which would be their own keys. When there is no value distinct from the key, this is sometimes known as a "set", and with a hash table implementation a "hash set". The defining quality of a hash table is that a hash function calculates an array index from the key data, with different keys tending to yield different indices, allowing constant time access to an array element likely to contain the key. That's an implementation / performance quality, rather than a functional quality like that defining a map.

So, a hash table stores elements, each of which need not consist of distinct key and value components, but if it does then it's also a hash map.

Foxing

So a hashmap is simply a particular type of a hash table (one which has distinct keys and values)? – Malissamalissia

@NickZuber: yes, that's correct - a reasonable paraphrasing of my final paragraph. Cheers – Foxing

Thank you for finally being the first person to clearly explain what the difference between a hash table and hashmap +1 – Malissamalissia

This is a high-quality answer but still misses to make the difference clear. In which situation we can implement what you explain as map(key-value) in a binary tree? why don''t people call just map instead of hashmap if the Computer Science definition is just like you explained being map? Your explanation os Hashtable is very ambiguous, it leaves margin the interpret there is no key-value, and that is not the case, your example simply communicates the key and value can be the same. – Emmalynne

@RollRoll: I've reread my answer and I think it's very clear, but I can see English isn't your first language, so let's work through your questions: "In which situation we can implement what you explain as map(key-value) in a binary tree?" - you can do that whenever the memory usage and performance implications of a binary tree are ok for your application. Using a tree (e.g. C++ std::map), you'll have O(log N) lookup, insertion and erase, whereas a hash table (std::unordered_map) has amortised O(1). Using a vector is most CPU cache friendly, and typically has lowest memory overheads. – Foxing

"why don't people call just map instead of hashmap if the Computer Science definition is just like you explained being map?" - if people know what they're talking about, they'll use "map" whenever they only care that it's an associative container (i.e. they can map from keys to values). They should only say "hashmap" if the implementation uses a hash table. – Foxing

"Your explanation os Hashtable is very ambiguous, it leaves margin the interpret there is no key-value, and that is not the case, your example simply communicates the key and value can be the same." - your complaint is ambiguous, what do you mean by "no key-value"? I have given an example { 1, 10, 33, 96 } showing a hash table may store a set of elements in which there are no distinct key and value components. Obviously given hashmaps exist, you can also store something like { 1->"one", 2->"two", 3->"three" } (to pick an arbitrary representation), with distinct keys and values. – Foxing

@TonyDelroy This to me is still somewhat confusing since if a data structure has no distinct key and value, what is the hash function applied to? I see that in the example given: {1,10,33,97} are considered their own keys. So then the hash function would be applied to them to retreive an index into an array containing what? If there is no value then there is nothing to retreive. Or are we hashing the key to get an index into an array that contains the key? Why would someone want to do that if they already have the key (since they were able to pass it to the hashing function in the first place) – Glendaglenden

@Horace: there are two main types of hash table: 1) separate chaining - where each bucket logically holds a container of elements that hashed to that bucket; in practice, the bucket might hold a pointer/iterator into a linked list, allowing traversal of that group of elements), or nullptr, and 2) open addressing, where the buckets are logically an "optional<element>". "If there is no value then there is nothing to retreive." true - a null pointer/iterator or false (or not-used element sentinel value). Why? To ask "is <key> already in the table?", or "erase <key> if it's in the table". – Foxing

@Horace: "If there is no value then there is nothing to retreive." - one other point on this: for hash maps, where there are keys and values, the buckets still link to or contain key/value elements, where the key appears. That's for exactly the same reason as in a hash set - you need to know that the hashing process has found the specific key you're interested in, rather than some other value whose key happened to have hash % bucket_count identify the same array index (i.e. to handle "collisions"). – Foxing

@TonyDelroy I understand, not long after posting that comment I looked into sets as data structures and was similarly stumped by their use. Why have a data structure where in order to access an element, you need to already have that same element. But it's indeed to ask: is the element in this set? I can see that being useful sometimes. It wasn't really the hash part of the data structure that stumped me, it was the functionality of sets in general. Now that I get that, this totally makes sense. A hash table is a specific implementation of a set. – Glendaglenden

Answer 2

Here's the way I understand it:
Hash Table: what we call the concept in Computer Science
Hash Map: what it is called in Java
Hash Set (HashSet): the case where we only care about the unique keys (or you can see it as a Hash Table where we ignore the values, we just want to know what is the set of unique keys)

Or simply,
Hash Table (CS) = HashMap (Java) = Dictionary (Python)
Hash Set (CS) = HashSet (Java) = Set (Python)

Twodimensional

I understand it like that exactly as well :) – Webster

Answer 3

C doesn't have any built-in containers (apart from arrays), so it's up to the individual implementor as to what they want to call it. As far as C is concerned, HashMap vs. HashTable have no real meaning.

One possible distinction may be in how the backing store is set up. A hash table may be a simple linear array of keys and values, indexed by hash. A hash map may be a balanced tree ordered by key, along with a table that maps the hash to the tree node, allowing for both fast (O(1)) lookup and the ability to traverse the data in key order.

Or it could be something completely different. Again, C doesn't have any sort of built-in container for this sort of thing, so the names don't really mean anything in a C context.

Perineuritis

Answer 4

The explaination between hashmap and hashtable is quite correct as it also fits to the header of a string hash map implementated in strmap.c where the stringmap is a hashtable for strings satisfying the properties of a key,value-structure. Here it says :

/*
 *    strmap version 2.0.1<br>
 *
 *    ANSI C hash table for strings.
 *
 *    Version history:
 *    1.0.0 - initial release
 *    2.0.0 - changed function prefix from strmap to sm to ensure
 *        ANSI C compatibility 
 *    2.0.1 - improved documentation<
 *
 *    strmap.c
 *
 *    Copyright (c) 2009, 2011, 2013 Per Ola Kristensson.
 *
 *    Per Ola Kristensson <[email protected]> 
 *    Inference Group, Department of Physics
 *    University of Cambridge
 *    Cavendish Laboratory
 *    JJ Thomson Avenue
 *    CB3 0HE Cambridge
 *    United Kingdom
 *
 *    strmap is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU Lesser General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    strmap is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Lesser General Public License for more details.
 *
 *    You should have received a copy of the GNU Lesser General Public License
 *    along with strmap.  If not, see <http://www.gnu.org/licenses/>.
 */
#include "strmap.h"
typedef struct Pair Pair;
typedef struct Bucket Bucket;
struct Pair {
    char *key;
    char *value;
};

Knighterrant

Answer 5

What I understand about the difference between Hashmap and Hashtable only from a Data Structure standpoint, disregarding technology implementing it is the following:

Hashmap: Is a higher-level Data Structure that organizes data in a key-value pair manner. Ex: yellow pages;

Hashtable: Is a type of Hashmap that the key information is directly related to the value, very often generated by applying a hashing function using the value as the source, but it doesn't have to be in order to be considered a hashtable. As mentioned above, having the same key as the value would be still consider hashtable.

Emmalynne