Data Structure - Hash Table

Hash Table:

The java.util.Hashtable class is a class in Java that provides a key-value data structure, similar to the Map interface. It was part of the original Java Collections framework and was introduced in Java 1.0.

Example:

Frequent examples of real-life problems where hash tables might be implemented are in phone number lookups, social security databases, libraries, and in username-password retrievals. In the phonebook example, the name would be the key and the number would be the value

Details:

However, the Hashtable class has since been considered obsolete and its use is generally discouraged. This is because it was designed prior to the introduction of the Collections framework and does not implement the Map interface, which makes it difficult to use in conjunction with other parts of the framework. In addition, the Hashtable class is synchronized, which can result in slower performance compared to other implementations of the Map interface.

In general, it’s recommended to use the Map interface or one of its implementations (such as HashMap or ConcurrentHashMap) instead of the Hashtable class.

In computation, a hash table is a type of data structure that is used in order to store and process information both quickly and efficiently. Hash tables are also sometimes called hash maps or dictionaries since they arrange data into map-like arrays.

Using keys and values, hash tables use hash functions to compute an index. These indexes are sometimes called hash codes. The information is then randomly sorted into an array of buckets or slots. During computation, the key will be hashed, and its randomly assigned index will indicate where in the array the value is stored. This structure is sometimes referred to simply as the key-value method.

Frequent examples of real-life problems where hash tables might be implemented are in phone number lookups, social security databases, libraries, and in username-password retrievals. In the phonebook example, the name would be the key and the number would be the value. In programming, the languages C++ and Java use hash tables as part of their standard libraries. Other languages such as Python and Go have built-in dictionaries and maps.

Difference Between Hashmap and Hashtable

S. No.	Hashmap	Hashtable
1.	No method is synchronized.	Every method is synchronized.
2.	Multiple threads can operate simultaneously and hence hashmap’s object is not thread-safe.	At a time only one thread is allowed to operate the Hashtable’s object. Hence it is thread-safe.
3.	Threads are not required to wait and hence relatively performance is high.	It increases the waiting time of the thread and hence performance is low.
4.	Null is allowed for both key and value.	Null is not allowed for both key and value. Otherwise, we will get a null pointer exception.
5.	It is introduced in the 1.2 version.	It is introduced in the 1.0 version.
6.	It is non-legacy.	It is a legacy.

Now you must be wondering why HashTable doesn’t allow null and HashMap do?

The answer is simple. In order to successfully store and retrieve objects from a HashTable, the objects used as keys must implement the hashCode method and the equals method. Since null is not an object, it can’t implement these methods. HashMap is an advanced version and improvement on the Hashtable. HashMap was created later.

Real World Examples:

Hash tables have a wide range of real-world applications. Here are some examples of how they are used at a societal level:

1. Databases: Hash tables are often used to implement databases, which are used by many organizations and businesses to store and manage large amounts of data. Frequent examples of real-life problems where hash tables might be implemented are in phone number lookups, social security databases, libraries, and in username-password retrievals. In the phonebook example, the name would be the key and the number would be the value.

1. Search engines: Search engines like Google and Bing use hash tables to quickly find relevant web pages based on search queries. The search engine creates a hash table of all the web pages it has indexed, with each entry in the table containing the URL of a web page and the keywords associated with that page.
   

2. Caching: Hash tables are often used in caching, which is the process of storing frequently accessed data in memory to improve performance. For example, a web browser might use a hash table to cache recently visited web pages, so that they can be quickly accessed the next time the user visits the site.

3. Cryptography: Hash tables are used in cryptography to create secure digital signatures and to verify the integrity of digital data. For example, a digital certificate might be signed using a hash table, which would ensure that the certificate has not been tampered with.

4. Computer networking: Hash tables are used in computer networking to implement routing tables, which are used by routers to determine the best path for data to travel through a network. For example, a router might use a hash table to store information about the various network segments it is connected to, along with information about the quality of each connection.

Overall, hash tables are a fundamental data structure that are used in many different fields and applications.

1. Lists:

• Real-time Task Management:

• Task management applications use lists to maintain ordered lists of tasks.

• Prioritizing, adding, and removing tasks can be efficiently handled with ArrayList or LinkedList.

2. Sets:

• Unique Usernames in a System:

• Sets ensure unique usernames in user databases.

• Checking for the existence of a username becomes an efficient operation with HashSet or TreeSet.

3. Queues:

• Print Job Queue in an Operating System:

• Operating systems use queues to manage print job requests.

• Jobs are processed in a first-come, first-served order using Queue implementations like LinkedList.

4. Maps:

• Geographical Information Systems:

• Maps are extensively used in GIS applications to associate geographical coordinates with specific data.

• HashMap or TreeMap can efficiently map coordinates to geographic information.

5. Stacks:

• Expression Evaluation in Programming:

• Stacks are employed in programming for expression evaluation (e.g., infix to postfix conversion).

• Stack implementations, such as ArrayDeque, facilitate efficient manipulation of expressions.

6. Deques:

• Undo Mechanism in Text Editors:

• Deques support undo mechanisms in text editors.

• Maintaining a history of actions can be efficiently handled with LinkedList or ArrayDeque.

7. PriorityQueues:

• Task Scheduling in Operating Systems:

• PriorityQueues are used in operating systems for task scheduling.

• Tasks with higher priority are processed first, ensuring efficient resource utilization.

8. LinkedHashMaps:

• Order-Preserving Caching:

• LinkedHashMaps can be used in caching scenarios where the order of access matters.

• Frequently accessed items are retained in the cache, ensuring quick retrieval.

9. TreeMap:

• Dictionary Applications:

• TreeMap is suitable for dictionary applications where words are mapped to their meanings.

• The TreeMap maintains a sorted order based on keys, facilitating efficient word lookup.

10. Hashtable:

• Databases:

• Hash tables are used to implement databases for quick data retrieval.

• Key-value pairs efficiently store information in applications such as phone number lookups and username-password retrievals.

Hashtable

package collectiondemos;

import java.util.Hashtable;

import java.util.Iterator;

import java.util.Map;

import java.util.Map.Entry;

import java.util.Set;

public class HashtableDemo {

    public static void main(String[] args) {

     //Hashtable t=new Hashtable();      

     Hashtable <String,String> t=new Hashtable<IString,String>();

     t.put("SDET120","Geekathon");

     t.put("SDET119","API Testing");

     t.put("DVLR10","Java");

               t.put("DA90","SQL Bootcamp"):                        

t.put("SDET87","Scraper Hackathon");

     //t.put(null,"X"); //NullPointerException

     //t.put(“SDET121”, null); //NullPointerException

     System.out.println(t); 

     System.out.println(t.get(“SDET119”)); 

     t.remove(“DVLR10”);

     System.out.println(t);     

     System.out.println(t.containsKey("SDET120")); //true

     System.out.println(t.containsKey("SDET121")); //false

     System.out.println(t.containsValue("Java")); //true

     System.out.println(t.containsValue("Python")); //False

     System.out.println(t.isEmpty());//false

     System.out.println(t.keySet());  //returns all the keys as Set 

     System.out.println(t.values()); //returns all the values as collection

     /*for(int k:t.keySet())

     {

     System.out.println(k+"   "+t.get(k));

     }*/

     //Entry specific methods...

     /*for(Map.Entry entry:t.entrySet()) // (key, value)

     {

     System.out.println(entry.getKey()+"   "+entry.getValue());

     }*/

     //iterator()

     Set s=t.entrySet();

     Iterator itr=s.iterator();

     while(itr.hasNext())

     {

     Map.Entry entry=(Entry) itr.next();   //(101,x)

     System.out.println(entry.getKey()+" "+entry.getValue());

     }

    }

}