Java Collections : HashTable

sequenceDiagram

   java.util.HashTable->>java.util.Dictionary:extends 
   java.util.HashTable->>java.util.Map:implements
   java.util.HashTable->>java.io.Serializable:implements
  java.util.HashTable->>java.lang.Cloneable:implements
  

public class Hashtable<K,V> extends Dictionary<K,V> 
		implements Map<K,V>, Cloneable, Serializable

HashTable

1. The Hashtable class implements a hash table.

2. A Hashtable is an array of a list. Each list is known as a Bucket. The position of the Bucket is identified by calling the HashCode() method.

3. Hashtable is synchronized.

4. Hashtable stores key/value pair in Hash Table.

5. A Hashtable contains values based on the key.

6. Java Hashtable class doesn't allow null key or value.

7. Java Hashtable class contains unique elements.

8. In Hashtable we specify an object that is used as a key, and the value we want to associate to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.

9. The initial default capacity of Hashtable class is 11.

10. The default loadFactor is 0.75 .

11. HashMap doesn’t provide any Enumeration, while Hashtable provides not fail-fast Enumeration.

Internal Workings of HashTable

Linked List



Buckets

1. As we can see that item composed of Key/Value = Item placed in each Slot / Bucket according to Index.



Process of Insertion of Keys and Values

2. Each Key is converted to Hash by calling hashcode() method.

3. Next each converted hash coded key modulo (%) with no. of slots present in the array of buckets from which we get index of the Bucket at which we can store that particular Key/Value pair . And this process continues for each Key-Value pair .

Example:

  
For A Key-Value pair :
  
Say Key is "A".
Hash Code is: 65 (ASCII)

Default Capacity of Hash Table = 11

Index = 65 % 11 = 10 of Bucket
  

Load Factor

Load Factor is calculated = Total No. of Entries in Hash Table / Total size of Hash Table.

Or Load Factor = Total number of Elements / (Total number of Buckets/Slots)

Suppose we need to enter 4 entries i.e., 4 is here the initial capacity or we can say total size of Hash Table. But we have entered 3 entries , hence ¾ = 0.75 (Load Factor).

Default No. of Buckets / Default Capacity of Hash Table = 11.

Default Load Factor of Hash Table = 0.75.

Need for Resizing of Bucket

Size of Hash Table(M) / No. of Buckets (N)> Load Factor = Need for Resizing.

Example:

We have Table say of 9 slots:



  
Now lets going with Default Load Factor and No. Of Buckets.
  
Say Hash Table has a Size = 1(Number of Entries):
   1 / 11 = 0.091 < 0.75


Say Hash Table has a Size = 9 (Number of Entries):
   9 / 11 = 0.818 > 0.75

Hence it needs a resize of Hash Table.
   
Therefore,Resized Bucket: 9 x 2 = 18 slots .
  

Hence increased Hash Table is:



Next such increase would be : 18 x2 = 36.

And so on….

But in Hash Table if 60% of Hash Table gets filled i.e. for default capacity 11 , it would be 6.6(6.6 /11 = 0.6 < 0.75) , Hash Table gets doubled. Here default threshold is 3/4 = 0.75 i.e. default load factor of Hash Table.

Re-Hashing

Basically, when the load factor increases to more than its pre-defined value (e.g. 0.75 as taken in above examples), the Time Complexity for search and insert increases.So to overcome this, the size of the array is increased(usually doubled) and all the values are hashed again and stored in the new double sized array to maintain a low load factor and low complexity. It copies all the element to a new array and make it the new bucket array.

Collision of Index

Definition: A collision occurs when two keys get mapped to the same index.

Handling Collisions

1. Linear Probing: If a Key - Value pair is hashed to a slot which is already occupied, it searches linearly for the next free slot in the table.

2. Chaining: During creation of Index, [ HashCode % No. Of Buckets = Index], if more than one index become same, then there creates a chance of collision. Hence it creates a Linked List on same index.

Suppose, Index of Key 3 (K3) and Index of Key 4(K4) = 2 . Then it creates a chance of collision, What it does is creating a Linked List at same index.



3. Maintaining Threshold: A hash table with a threshold of 0.6 would resize when 60% of the space is occupied. As a convention, the size of the hash table is doubled. This can be memory intensive.

HashTable - A Thread Safe Property

1. Hashtable is synchronized and offers thread safety comparable to concurrentHashMap.

2. Hashtable writes operations employ hashtable wide lock, which locks the whole hashtable object.

Strengths And Weaknesses of Hash Table

Time Complexity
Operation	Average	Worst
Search	O(1)	O(n)
Insertion	O(1)	O(n)
Deletion	O(1)	O(n)
Space	O(n)	O(n)

Strengths of Hash Table

1. Fast lookups : Lookups take O(1) time on average.

2. Flexible keys : Most data types can be used for keys, as long as they’re hashable .

Weakness of Hash Table

1. Slow worst-case lookups : Lookups take O(n) time in the worst case .

2. Unordered : Keys aren’t stored in a special order. If you’re looking for the smallest key, the largest key, or all the keys in a range, you’ll need to look through every key to find it.

3. Single-directional lookups : While we can look up the value for a given key in O(1) time, looking up the keys for a given value requires looping through the whole dataset—O(n) time.

4. Not cache-friendly : Many hash table implementations use linked lists , which don’t put data next to each other in memory.

Constructors of Hash Table

• 1. Hashtable()

It creates an empty hashtable having the initial default capacity and load factor.

• 2. Hashtable(int capacity)

It accepts an integer parameter and creates a hash table that contains a specified initial capacity.

• 3. Hashtable(int capacity, float loadFactor)

It is used to create a hash table having the specified initial capacity and loadFactor.

• 4. Hashtable(Map m)

It creates a new hash table with the same mappings as the given Map.

Constructors	Does This
Hashtable()	It creates an empty hashtable having the initial default capacity and load factor.
Hashtable(int capacity)	It accepts an integer parameter and creates a hash table that contains a specified initial capacity.
Hashtable(int capacity, float loadFactor)	It is used to create a hash table having the specified initial capacity and loadFactor.
Hashtable(Map m)	It creates a new hash table with the same mappings as the given Map.

Methods of Hash Table

• 1.Methods of Hash Table

Note : These methods are already discussed 👉: Here

• 2.ReHash()

Increases the capacity of and internally reorganizes this hashtable, 
in order to accommodate and access its entries more efficiently.

New Method/s	Does This
ReHash()	Increases the capacity of and internally reorganizes this hashtable, in order to accommodate and access its entries more efficiently.

Diagram of HashTable

 
 graph TD;
    Map-->|implements| HashTable;
    Serializable -->|implements| HashTable;
    Clonable -->|implements| HashTable;
    Dictionary -->|extends| HashTable;
    HashTable -->|extends| Properties;
    HashTable -->|extends| UIDefaults;

A. UIDefaults Class

sequenceDiagram

   javax.swing.UIDefaults->>java.util.HashTable:extends 
  

public class UIDefaults extends Hashtable<Object,Object>

1. Def: A table of defaults for Swing components. Applications can set/get default values via the UIManager.

2. UIDefaults have some nested classes as discussed below .

Diagram of Nested Classes of UIDefaults

 
 graph TD;
 UIDefaults-->|NestedClass| UIDefaults.ActiveValue;
 UIDefaults-->|NestedClass| UIDefaults.LazyInputMap;
 UIDefaults-->|NestedClass| UIDefaults.LazyValue;
 UIDefaults-->|NestedClass| UIDefaults.ProxyLazyValue;

Description of Nested Classes of UIDefaults

1. UIDefaults.ActiveValue

public static interface UIDefaults.ActiveValue

It is an interface class. This class enables one to store an entry in the defaults table that's constructed each time it's looked up with one of the getXXX(key) methods.It have createValue(UIDefaults table) method which creates the value retrieved from the UIDefaults table.

Implementation of UIDefaults.ActiveValue Nested Class.

Method/s	Does This
createValue(UIDefaults table)	Creates the value retrieved from the UIDefaults table.

2. UIDefaults.LazyInputMap

public static class UIDefaults.LazyInputMap extends Object
                         implements UIDefaults.LazyValue

The bindings are passed in in the constructor. The bindings are an array with the even number entries being string KeyStrokes (eg "alt SPACE") and the odd number entries being the value to use in the InputMap (and the key in the ActionMap).

Implementation of UIDefaults.LazyInputMap Nested Class.

Method/s	Does This
createValue(UIDefaults table)	Creates the value retrieved from the UIDefaults table.

3. UIDefaults.LazyValue

public static interface UIDefaults.LazyValue

This class enables one to store an entry in the defaults table that isn't constructed until the first time it's looked up with one of the getXXX(key) methods. Lazy values[A value which may be lazily computed] are useful for defaults that are expensive to construct or are seldom retrieved. The first time a LazyValue is retrieved its "real value" is computed by calling LazyValue.createValue() and the real value is used to replace the LazyValue in the UIDefaults table. Subsequent lookups for the same key return the real value.

Implementation of UIDefaults.LazyValue Nested Class.

Method/s	Does This
createValue(UIDefaults table)	Creates the value retrieved from the UIDefaults table.

4. UIDefaults.ProxyLazyValue

public static class UIDefaults.ProxyLazyValue
		extends Object
		implements UIDefaults.LazyValue

This class provides an implementation of LazyValue which can be used to delay loading of the Class for the instance to be created. It also avoids creation of an anonymous inner class for the LazyValue subclass.

Implementation of UIDefaults.ProxyLazyValue Nested Class.

Constructor	Description
UIDefaults.ProxyLazyValue(String c)	Creates a LazyValue which will construct an instance when asked.
UIDefaults.ProxyLazyValue(String c, Object[] o)	Creates a LazyValue which will construct an instance when asked.
UIDefaults.ProxyLazyValue(String c, String m)	Creates a LazyValue which will construct an instance when asked.
UIDefaults.ProxyLazyValue(String c, String m, Object[] o)	Creates a LazyValue which will construct an instance when asked.

Method/s	Does This
createValue(UIDefaults table)	Creates the value retrieved from the UIDefaults table.

Constructors of UIDefaults

1. UIDefaults()

Creates an empty defaults table.

2. UIDefaults(int initialCapacity, float loadFactor)

Creates an empty defaults table with the specified initial capacity and load factor.

3. UIDefaults(Object[] keyValueList)

Creates a defaults table initialized with the specified key/value pairs.

Constructor	Description
UIDefaults()	Creates an empty defaults table.
UIDefaults(int initialCapacity, float loadFactor)	Creates an empty defaults table with the specified initial capacity and load factor.
UIDefaults(Object[] keyValueList)	Creates a defaults table initialized with the specified key/value pairs.

Methods of UIDefaults class

• 1. Methods of UIDefaults class that falls under Java Swing

1. a. Methods of UIDefaults class that falls under Java Swing

Method/s	Description
1. addPropertyChangeListener(PropertyChangeListener listener)	Adds a PropertyChangeListener to the listener list.
2. addResourceBundle(String bundleName)	Adds a resource bundle to the list of resource bundles that are searched for localized values.
3.get(Object key)	Returns the value for key.
4.get(Object key, Locale l)	Returns the value for key associated with the given locale.
5.getBoolean(Object key)	If the value of key is boolean, return the boolean value, otherwise return false.
6. getBoolean(Object key, Locale l)	If the value of key for the given Locale is boolean, return the boolean value, otherwise return false.
7. getBorder(Object key)	If the value of key is a Border return it, otherwise return null.
8. getBorder(Object key, Locale l)	If the value of key for the given Locale is a Border return it, otherwise return null.
9. getColor(Object key)	If the value of key is a Color return it, otherwise return null.
10. getColor(Object key, Locale l)	If the value of key for the given Locale is a Color return it, otherwise return null.
11. getDefaultLocale()	Returns the default locale.
12. getDimension(Object key)	If the value of key is a Dimension return it, otherwise return null.
13. getDimension(Object key, Locale l)	If the value of key for the given Locale is a Dimension return it, otherwise return null.
14. getFont(Object key)	If the value of key is a Font return it, otherwise return null.
15. getFont(Object key, Locale l)	If the value of key for the given Locale is a Font return it, otherwise return null.
16. getIcon(Object key)	If the value of key is an Icon return it, otherwise return null.
17. getIcon(Object key, Locale l)	If the value of key for the given Locale is an Icon return it, otherwise return null.
18. getInsets(Object key)	If the value of key is an Insets return it, otherwise return null.
19. getInsets(Object key, Locale l)	If the value of key for the given Locale is an Insets return it, otherwise return null.
20. getInt(Object key)	If the value of key is an Integer return its integer value, otherwise return 0.
21. getInt(Object key, Locale l)	If the value of key for the given Locale is an Integer return its integer value, otherwise return 0.
22. getPropertyChangeListeners()	Returns an array of all the PropertyChangeListeners added to this UIDefaults with addPropertyChangeListener().
23. getString(Object key)	If the value of key is a String return it, otherwise return null.
24. getString(Object key, Locale l)	If the value of key for the given Locale is a String return it, otherwise return null.
25. getUI(JComponent target)	Creates an ComponentUI implementation for the specified component.
26. getUIClass(String uiClassID)	Returns the Look And Feel class that renders this component.
27. getUIClass(String uiClassID, ClassLoader uiClassLoader)	The value of get(uidClassID) must be the String name of a class that implements the corresponding ComponentUI class.
28. put(Object key, Object value)	Puts all of the key/value pairs in the database and unconditionally generates one PropertyChangeEvent.
29. putDefaults(Object[] keyValueList)	Puts all of the key/value pairs in the database and unconditionally generates one PropertyChangeEvent.
30. removePropertyChangeListener(PropertyChangeListener listener)	Removes a PropertyChangeListener from the listener list.
31. removeResourceBundle(String bundleName)	Removes a resource bundle from the list of resource bundles that are searched for localized defaults.
32. setDefaultLocale(Locale l)	Sets the default locale.

1. b. Implementation of firePropertyChange And getUIError

Method/s	Description
1. firePropertyChange(String propertyName, Object oldValue, Object newValue)	Support for reporting bound property changes.
2. getUIError(String msg)	If getUI() fails for any reason, it calls this method before returning null.

Note:The focus is on implentation of the methods rather than going deeper to Java Swing package.

• 2. Methods of UIDefaults class that falls under Java HashTable

• 2.a Methods of UIDefaults class that falls under Java HashTable

• 2.b Implementation of ReHash method in UIDefaults class

Note:These methods are already discussed earlier.

B. Properties Class

sequenceDiagram

   java.util.Properties->>java.util.HashTable:extends 
  

public class Properties extends Hashtable<Object,​Object>

• 1. The Properties class is a subclass of Hashtable.

• 2. The Properties class represents a persistent set of properties.

• 3. The Properties can be saved to a stream or loaded from a stream.

• 4. The Properties class belongs to java.util package.

• 5. The properties object contains key and value pair both as a string.

• 6. The Properties class can be used to get property value based on the property key.

• 7. The Properties class provides methods to get data from the properties file and store data into the properties file.

• 8. The Properties class can be used to get the properties of a system.

• 9. The Properties class is used to maintain a list of values in which the key is a string and the value is also a string i.e; it can be used to store and retrieve string type data from the properties file.

• 10. The Properties class can specify other properties list as it’s the default. If a particular key property is not present in the original Properties list, the default properties will be searched.

• 11. The object of Properties class does not require external synchronization and Multiple threads can share a single Properties object.

Constructor of Properties Class

• 1. Properties()

It creates an empty property list with no default values.

• 2. Properties(int initialCapacity)

It creates an empty property list with an initial capacity and
no default values.

• 3. Properties(Properties defaults)

It creates an empty property list with the specified defaults,
of Property object.

Constructors	Description
Properties(int initialCapacity)	It creates an empty property list with an initial capacity and no default values.
Properties(Properties defaults)	It creates an empty property list with the specified defaults, of Property object.

Methods of Properties Class

• 1.Methods of Properties Class

• 1. getProperty​(String key)

Searches for the property with the specified key in this property list.

• 2. getProperty​(String key, String defaultValue)

Searches for the property with the specified key in this property list.

• 3. list​(PrintStream out)

Prints this property list out to the specified output stream.

• 4. list​(PrintWriter out)

Prints this property list out to the specified output stream.

• 5. load​(InputStream inStream)

Reads a property list (key and element pairs) from the input byte stream.

• 6. load​(Reader reader)

Reads a property list (key and element pairs) ,
from the input character stream in a simple line-oriented format.

• 7. loadFromXML​(InputStream in)

Loads all of the properties represented by the XML document ,
on the specified input stream into this properties table.

Note: In XML file,
<!DOCTYPE properties SYSTEM "http://java.sun.com/dtd/properties.dtd">
is compulsory.

• 8. propertyNames()

Returns an enumeration of all the keys in this property list, 
including distinct keys in the default property list,
if a key of the same name has not already been found,
from the main properties list.

• 9. store​(OutputStream out, String comments)

Writes this property list (key and element pairs) in this Properties table ,
to the output stream in a format suitable for loading into a ,
Properties table using the load(InputStream) method.

• 10. save​(OutputStream out, String comments)

This method does not throw an IOException ,
if an I/O error occurs while saving the property list.

It is Deprecated.

• 11. setProperty​(String key, String value)

Calls the Hashtable method put.

• 12. store​(Writer writer, String comments)

Writes this property list (key and element pairs) in this Properties table ,
to the output character stream in a format ,
suitable for using the load(Reader) method.

• 13. storeToXML​(OutputStream os, String comment)

Emits an XML document representing all of the properties
contained in this table.

• 14. storeToXML​(OutputStream os, String comment, String encoding)

Emits an XML document representing all of the properties contained in this table, 
using the specified encoding.

• 15. storeToXML​(OutputStream os, String comment, Charset charset)

Emits an XML document representing all of the properties contained in this table, 
using the specified encoding.

• 16. stringPropertyNames()

Returns an unmodifiable set of keys from this property list where the key 
and its corresponding value are strings, including distinct keys in the,
default property list if a key of the same name has not already been found,
from the main properties list.

Methods of Properties	Description
1.getProperty​(String key)	Searches for the property with the specified key in this property list.
2. getProperty​(String key, String defaultValue)	Searches for the property with the specified key in this property list.
3. list​(PrintStream out)	Prints this property list out to the specified output stream.
4. load​(InputStream inStream)	Reads a property list (key and element pairs) from the input byte stream.
5. load​(Reader reader)	Reads a property list (key and element pairs) ,from the input character stream in a simple line-oriented format.
6. loadFromXML​(InputStream in)	Loads all of the properties represented by the XML document ,on the specified input stream into this properties table.
7. loadFromXML​(InputStream in)	Loads all of the properties represented by the XML document ,on the specified input stream into this properties table.Note: In XML file, is compulsory.
8. propertyNames()	Returns an enumeration of all the keys in this property list, including distinct keys in the default property list, if a key of the same name has not already been found,from the main properties list.
9. store​(OutputStream out, String comments)	Writes this property list (key and element pairs) in this Properties table , to the output stream in a format suitable for loading into a , Properties table using the load(InputStream) method.
10. save​(OutputStream out, String comments)	This method does not throw an IOException , if an I/O error occurs while saving the property list. It is Deprecated.
11. setProperty​(String key, String value)	Calls the Hashtable method put.
12. store​(Writer writer, String comments)	Emits an XML document representing all of the properties contained in this table.
13. storeToXML​(OutputStream os, String comment)	Emits an XML document representing all of the properties contained in this table.
14. storeToXML​(OutputStream os, String comment, String encoding)	Emits an XML document representing all of the properties contained in this table, using the specified encoding.
15. storeToXML​(OutputStream os, String comment, Charset charset)	Emits an XML document representing all of the properties contained in this table, using the specified encoding.
16. stringPropertyNames()	Returns an unmodifiable set of keys from this property list where the key and its corresponding value are strings, including distinct keys in the, default property list if a key of the same name has not already been found, from the main properties list.

• 2. Methods Inherited from HashTable Class in Properties Class

• 1. Methods Inherited from HashTable Class in Properties Class

• 2. Implementation of Rehash() Method.

Note : These methods are already discussed 👉: Here