# The fundamentals of Hash tables?

I'm quite confused about the basic concepts of a Hash table. If I were to code a hash how would I even begin? What is the difference between a Hash table and just a normal array?

Basically if someone answered this question I think all my questions would be answered: If I had 100 randomly generated numbers (as keys), how would I implement a hash table and why would that be advantageous over an array?

Psuedo-code or Java would be appreciated as a learning tool...

Asked by: Arnold900 | Posted: 23-01-2022

The answers so far have helped to define hash tables and explain some theory, but I think an example may help you get a better feeling for them.

What is the difference between a hash table and just a normal array?

A hash table and an array are both structures that allow you to store and retrieve data. Both allow you to specify an index and retrieve a value associated with it. The difference, as Daniel Spiewak noted, is that the indices of an array are sequential, while those of a hash table are based on the value of the data associated with them.

Why would I use a hash table?

A hash table can provide a very efficient way to search for items in large amounts of data, particularly data that is not otherwise easily searchable. ("Large" here means ginormous, in the sense that it would take a long time to perform a sequential search).

If I were to code a hash how would I even begin?

No problem. The simplest way is to invent an arbitrary mathematical operation that you can perform on the data, that returns a number `N` (usually an integer). Then use that number as the index into an array of "buckets" and store your data in bucket #`N`. The trick is in selecting an operation that tends to place values in different buckets in a way that makes it easy for your to find them later.

Example: A large mall keeps a database of its patrons' cars and parking locations, to help shoppers remember where they parked. The database stores `make`, `color`, `license plate`, and `parking location`. On leaving the store a shopper finds his car by entering the its make and color. The database returns a (relatively short) list of license plates and parking spaces. A quick scan locates the shopper's car.

You could implement this with an SQL query:

``````SELECT license, location FROM cars WHERE make="\$(make)" AND color="\$(color)"
``````

If the data were stored in an array, which is essentially just a list, you can imagine implementing the query by scanning an array for all matching entries.

On the other hand, imagine a hash rule:

Add the ASCII character codes of all the letters in the make and color, divide by 100, and use the remainder as the hash value.

This rule will convert each item to a number between 0 and 99, essentially sorting the data into 100 buckets. Each time a customer needs to locate a car, you can hash the make and color to find the one bucket out of 100 that contains the information. You've immediately reduced the search by a factor of 100!

Now scale the example to huge amounts of data, say a database with millions of entries that is searched based on tens of criteria. A "good" hash function will distribute the data into buckets in a way that minimizes any additional searching, saving a significant amount of time.

First, you have to understand a what a hash function is. A hash function is a function that takes a key (for example, an string of arbritrary length) and returns a number as unique as possible. The same key must always return the same hash. A really simple string hashing function in java might look like

``````public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
``````

You can study a good hash function at http://www.azillionmonkeys.com/qed/hash.html

Now, the hash map uses this hash value to place the value into an array. Simplistic java method:

``````public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
}
``````

(This map enforces unique keys. Not all maps do.)

It is possible for two different keys to hash to the same value, or two different hashes to map to the same array index. There exists many techniques for dealing with this. The simplest is to use a linked list (or binary tree) for each array index. If the hash function is good enough, you will never need a linear search.

Now to look up a key:

``````public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}

return null;
}
``````

Answered by: Roman412 | Posted: 24-02-2022

Hashtables are associative. This is a huge difference from arrays, which are just linear data structures. With an array, you might do something like this:

``````int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
``````

Notice how you are getting an element out of the array by specifying an exact memory offset (`i`). This contrasts with hashtables, which allow you to store key/value pairs, later retrieving the value based on the key:

``````Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
``````

With the above table, we can make the following call:

``````int n = table.get("Chris");
``````

...and be assured that `n` will be valued at `18`.

I think this will probably answer most of your questions. The implementation of a hashtable is a fairly interesting topic, one which Wikipedia addresses passably well.

Answered by: Vanessa840 | Posted: 24-02-2022

"I'm more interested in the way Hash Tables look up the key and how the key is generated."

1. Hashing transforms a key object to a number. This is called "hashing" -- it makes a hash out of the object. See Hash Function. Summing the bytes of a string, for example, is a standard hash technique. You compute the sum modulo 232 to keep the hash to a manageable size. Hash always gives the same answer. This is O(1).

2. The number gives you a "slot" in the HashTable. Given an arbitrary key object, the hash value computes a hash value. The hash value then gives you the slot in table. Usually `mod( hash, table size )`. This is O(1), also.

That's the general solution. Two numeric calculations and you've gone from arbitrary object as key to arbitrary object as value. Few things can be as fast.

The transformation from object to hash value happens in one of these common ways.

1. If it's a "primitive" object of 4 bytes, then the object's native value is a number.

2. The object's address is 4 bytes, then the object's address can be used as a hash value.

3. A simple hash function (MD5, SHA1, whatever) accumulates the bytes of the object to create a 4-byte number. The advanced hashes aren't simple sums of bytes, a simple sum doesn't reflect all the original input bits fairly enough.

The slot in the hash table is mod( number, size of table ).

If that slot has the desired value, you're done. If that's not the desired value, you need to look somewhere else. There are several popular probing algorithms to look for a free spot in the table. Linear is a simple search for the next free spot. Quadratic is a non-linear hopping around looking for a free slot. A random number generator (with a fixed seed) can be used to generate a series of probes that will spread data evenly but arbitrarily.

The probing algorithms are not O(1). If the table's big enough, the odds of collision are low, and probes don't matter. If the table's too small, then collisions happen and probing happens. At that point, it becomes a matter of "tuning and tweaking" to balance probing and table size to optimize performance. Usually we just make the table bigger.

See Hash Table.

Answered by: Julia628 | Posted: 24-02-2022

Something I didn't see specifically noted yet:

The point of using a hash table over an array is performance.

Iterating through an array would typically take anywhere from O(1) to O(x) where x is the number of items in the array. However the time to find your item will be extremely variable, expecially if we are talking about hundreds of thousands of items in the array.

A properly weighted hash table typically has an almost constant access time of just over O(1), no matter how many items are in the hash table.

Answered by: Lily330 | Posted: 24-02-2022

You wouldn't want to use a hash table for 100 randomly generated numbers.

A good way to think about hash tables is to think about value pairs. Let's use students, and say everyone has a student ID number. In your program you store information on students (names, phone numbers, bills, etc). You want to find all of the information about a student using only basic information (name or student ID, for example).

Let's say you have 10,000 students. If you store them all in an array, then you have to loop through the entire array comparing each entry's student ID with the one you are looking for.

If, instead, you "hash" (see below) their student ID number to a position in the array, then you only have to search student's who's numbers have the same hash. Much less work to find what you wanted.

In this example, let's say student IDs are just 6 digit numbers. Our hash function could be use only the bottom 3 digits of the number as the "hash key". Thus 232145 is hashed to array location 145. So then you only need an array of 999 element (each element being a list of students).

That should be a good start for you. You should, of course, read a text book or wikipedia for this kind of info. But I assume you've already done that and are tired of reading.

Answered by: Audrey369 | Posted: 24-02-2022

Here is, in short, how a hash table works.

Imagine you have a library, full of books. If you were to store the books in an array, you would put each book on a spot on a shelf, and then when someone asked you to find a book, you'd look through all the shelves -- pretty slow. If someone said "book #12345", you could find it pretty easily, though.

Let's say instead you say, if the book title starts with 'A', it goes in row 1. If the second letter is 'B', it goes in row 1, rack 2. If the third letter is 'C', it goes in row 1, rack 2, shelf 3... and so on until you identify the book position. Then, based on the title of the book, you could know exactly where it should be.

Now, there are some problems in the simplistic "hashing" algorithm I described -- some shelves are going to be way overloaded while others stand empty, some books will be assigned to the same slot.. so the real hash functions are carefully constructed to try to avoid such problems.

But this is the basic idea.

Answered by: Blake434 | Posted: 24-02-2022

I'll answer that part about the difference between a hash table and an array... but since I've never implemented a hashing algorithm of any import before, I'll leave that to somebody more knowledgeable :)

An array is just an ordered list of objects. The object itself doesn't really matter... what's important is that if you want to list the objects in order of insertion, it is always the same (meaning that the first element always has an index of 0).

As for a hashtable, that's indexed by keys, not order... I think that a basic search on hashing algorithms will give you a lot more insight than I can... Wikipedia has a very decent one... that determines "bucket" that the keys go into for quick retrieval on arbitrary objects used as keys.

As for advantages: If order of insertion is important, an array or some kind of ordered list is necessary. If fast look-up by arbitrary key (keyed by various hash functions) is important, then a hash table makes sense.

Answered by: Fenton437 | Posted: 24-02-2022

That depends on your hash function. Lets suppose that your hash function hashes a word as per the length of your word, the key for chris will be 5. Similarly, key for yahoo will also be 5. Now, both values (chris and yahoo) will go under 5 (i.e. in a 'bucket' keyed by 5). This way you don't have to make an array equal to the size of your data.

Answered by: Catherine645 | Posted: 24-02-2022

The question, I believe, is answered quite clearly and in many different ways by now.

I would just like to add another perspective (which may confuse a new reader as well)

At a level of least abstraction, arrays are just contiguous block of memory. Given the starting address (`startAddress`), size (`sizeOfElement`) and the `index` of a single element, the address of element is computed as:

``````elementAddress = startAddress + sizeOfElement * index
``````

The interesting thing to note here is that arrays can be abstracted/viewed as hash tables with `index` as key and the above function as a hash function which calculates the location of a value in O(1)

Answered by: Carina656 | Posted: 24-02-2022

Hash table is a data structure that is created for quick look up.

The hash tables are not effective when the number of entries are very small.

reference

Some examples:

``````    import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;

public class HashtableDemo {

public static void main(String args[]) {

// Creating Hashtable for example

Hashtable companies = new Hashtable();

// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");

// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));

// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

Enumeration enumeration = companies.elements();

while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}

// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

System.out.println("Is companies hashtable empty: "+companies.isEmpty());

// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

System.out.println("Size of hashtable in Java: " + companies.size());

// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

Set hashtableKeys = companies.keySet();

// you can also get enumeration of all keys by using method keys()

Enumeration hashtableKeysEnum = companies.keys();

// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

Enumeration hashtableValuesEnum = companies.elements();

Collection hashtableValues = companies.values();

// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

companies.clear();
}
}
``````

Output:

``````Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3
``````

Answered by: Charlie790 | Posted: 24-02-2022

# Similar questions

Knowing the fundamentals of Java what is the right approach to learn Groovy?

As my question already implies I want to learn a new language and have read several articles about groovy and its more pragmatic syntax. SO I have choosen Groovy as the language of my choice. What is a good way to learn a new language like Groovy when I already know the fundamentals of Java. When I understand correctly Groovy will be running in the Java Virtual Machine and allows me to always rely on what I know f...

Could I start off with UML classes before having classes in Java fundamentals?

In reality i won a scholarship at New Horizon in Java, (Getting to the point) there was predefined paradigm that we supposed to start with : Fundamentals of the Java Programming Language &lt;SL-110-SE6&gt; Java Programming Language (SL-275-SE6) Object-Oriented Analysis and Design Using UML (OO-226-SE6) Developing Applications With the Java SE Platform (SL-285-SE6) Developing Applications for the Java EE Pl...

primitive - Java confusion on fundamentals on double and integer and conversions

I am practicing in an automatic judge for algorithm in one of the carreer sites and I have the following question. In one of the puzzles the question is to find the median of 2 sorted arrays and the signature of the method to implement is: public double findMedianSortedArrays(int A[], int B[]) I written the code and some of the tests failed. Looking at the results though the fa...

java - Fundamentals on Generics

Why does the following does not work? Vector&lt;? extends SomeClass&gt; v = new Vector&lt;SomeClass&gt;(); SomeClass e = new SomeClass(); v.add(e); I get a compilation error that: The method add(capture#1-of ? extends SomeClass) in the type Vector is not applicable for the arguments (SomeClass)

java generic method fundamentals

i am running some tests to better understand java generic methods, and came across the following problem. i have the following simple class: 1 public class SomeClass&lt;O extends Object&gt; { 2 3 O someVar; 4 5 public SomeClass() { 6 someFunc(new Number(1)); 7 } 8 9 public void someFunc(O arg) { 10 // code 11 } 12 } a...

Java annotations fundamentals

I am a newbie to annotations. I have gone through a lot of tutorials explaining the concept of annotations. But nowhere do i find information about defining multiple annotations within a class. So pls give me some insight on defining and accessing multiple annotations.Below is the code where I define two annotations in a class and eclipse IDE presents me an error "The public type SampleAnn must be defined in its own file"....

java - Trouble Grapsing Dagger Fundamentals

I am attempting to use Dagger as my Android app's dependency injection library. In my project, I have different Android modules in the project representing different flavors of the app. I want to use dependency injection to allow each module to define its own navigation menu. My MenuFragment class requires an instance of my interface (MenuAdapterGenerator): public class MenuFragment extends Fragment...

java - UnitTesting Fundamentals - What exactly to test?

I have basic question. Java provides encapsulation to hide data from outside world and provide appropriate access using access modifiers. Then java introduced reflection which allows you to access everything available on class from anywhere. i am wondering why there is need to providing reflection.

I am having trouble deleting a node from Binary search tree. I guess I have not understood the fundamentals of how Java objects work

Node Class:- public class Node { int data; Node left; Node right; Node(int data){ this.data = data; left = null; right = null; } } BST Class:- public class BST { Node root; BST(){ root = null; } void insertNode(int data){ root = insertRecursive(data, root); } private Node insertRecursive(in...

# Still can't find your answer? Check out these amazing Java communities for help...

Java Reddit Community | Java Help Reddit Community | Dev.to Java Community | Java Discord | Java Programmers (Facebook) | Java developers (Facebook)