-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Avinandan Bose edited this page Jan 31, 2023
·
1 revision
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
- 1. The Hashtable class implements a hash table.
- 1. As we can see that item composed of Key/Value = Item placed in each Slot / Bucket according to Index.
- 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 .
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 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.
- Size of Hash Table(M) / No. of Buckets (N)> Load Factor = Need for Resizing.
- 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 .
- 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.
- Definition: A collision occurs when two keys get mapped to the same index.
- 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.
- 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.
- 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 .
- 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.
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) |
It creates an empty hashtable having the initial default capacity and load factor.
It accepts an integer parameter and creates a hash table that contains a specified initial capacity.
It is used to create a hash table having the specified initial capacity and loadFactor.
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 extends K,? extends V> m) | It creates a new hash table with the same mappings as the given Map. |
Note : These methods are already discussed 👉: Here
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. |
graph TD;
Map-->|implements| HashTable;
Serializable -->|implements| HashTable;
Clonable -->|implements| HashTable;
Dictionary -->|extends| HashTable;
HashTable -->|extends| Properties;
HashTable -->|extends| UIDefaults;
sequenceDiagram
javax.swing.UIDefaults->>java.util.HashTable:extends
- 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 .
graph TD;
UIDefaults-->|NestedClass| UIDefaults.ActiveValue;
UIDefaults-->|NestedClass| UIDefaults.LazyInputMap;
UIDefaults-->|NestedClass| UIDefaults.LazyValue;
UIDefaults-->|NestedClass| UIDefaults.ProxyLazyValue;
- 1. UIDefaults.ActiveValue
- Implementation of UIDefaults.ActiveValue Nested Class.
- 2. UIDefaults.LazyInputMap
- Implementation of UIDefaults.LazyInputMap Nested Class.
- 3. UIDefaults.LazyValue
- Implementation of UIDefaults.LazyValue Nested Class.
- 4. UIDefaults.ProxyLazyValue
- Implementation of UIDefaults.ProxyLazyValue Nested Class.
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.
Method/s | Does This |
---|---|
createValue(UIDefaults table) | Creates the value retrieved from the UIDefaults table. |
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).
Method/s | Does This |
---|---|
createValue(UIDefaults table) | Creates the value retrieved from the UIDefaults table. |
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.
Method/s | Does This |
---|---|
createValue(UIDefaults table) | Creates the value retrieved from the UIDefaults table. |
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.
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. |
Creates an empty defaults table.
Creates an empty defaults table with the specified initial capacity and load factor.
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. |
- 1. a. Methods of UIDefaults class that falls under Java Swing
- 1. b. Implementation of firePropertyChange And getUIError
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. |
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. |
sequenceDiagram
java.util.Properties->>java.util.HashTable:extends
It creates an empty property list with no default values.
It creates an empty property list with an initial capacity and
no default values.
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. |
Searches for the property with the specified key in this property list.
Searches for the property with the specified key in this property list.
Prints this property list out to the specified output stream.
Prints this property list out to the specified output stream.
Reads a property list (key and element pairs) from the input byte stream.
Reads a property list (key and element pairs) ,
from the input character stream in a simple line-oriented format.
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.
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.
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.
This method does not throw an IOException ,
if an I/O error occurs while saving the property list.
It is Deprecated.
Calls the Hashtable method put.
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.
Emits an XML document representing all of the properties
contained in this table.
Emits an XML document representing all of the properties contained in this table,
using the specified encoding.
Emits an XML document representing all of the properties contained in this table,
using the specified encoding.
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. |