Skip to content

Latest commit

 

History

History
288 lines (164 loc) · 16.8 KB

Map.md

File metadata and controls

288 lines (164 loc) · 16.8 KB
Raw

Map

Definition

Map, also known as a dictionary or associative array, is a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

Map

Operations associated with this data type allow:

  • Add or insert: add a new (key, value) pair to the collection, mapping the new key to its new value.
  • Reassign: replace the value in one of the (key, value) pairs that are already in the collection, mapping an old key to a new value.
  • Remove or delete: remove a (key, value) pair from the collection, unmapping a given key from its value.
  • Lookup: find the value (if any) that is bound to a given key.

HashTable Implementations

HashTable

The most frequently used general-purpose implementation of an associative array or map is with a hash table: an array combined with a hash function that separates each key into a separate "bucket" of the array. The basic idea behind a hash table is that accessing an element via its index is a simple, constant-time operation. Therefore, the average overhead of an operation for a hash table is only the computation of the key's hash, combined with accessing the corresponding bucket within the array. As such, hash tables usually perform in O(1) time, and outperform alternatives in most situations.

Hash Function

The hash function is a function that can be used to map data of arbitrary size to fixed-size values.

index = f(key, array_size)

A critical statistic for a hash table is the load factor, defined as

load_factor = the number of entries occupied in the hash table / the number of buckets

As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used). The expected constant time property of a hash table assumes that the load factor is kept below some bound.

Collision

Hash tables need to be able to handle collisions: when the hash function maps two different keys to the same bucket of the array. The two most widespread approaches to this problem are separate chaining and open addressing.

HashTable Separate Chaining

Separate chaining with linked lists makes each cell of the hash table point to a linked list of records that have the same hash function value. Chaining is simple but requires additional memory outside the table.

Some chaining implementations store the first record of each chain in the slot array itself, known as separate chaining with list head cells.

HashTable Open Addressing

Open addressing stores all elements in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, it examines table slots until the desired element is found or it is clear that the element is not in the table.

A drawback of all these open addressing schemes is that the number of stored entries cannot exceed the number of slots in the bucket array.

Best Practice

  • Use Double/Float as hashmap keys is a bad practice. Especially if you need to perform calculations on double keys, the hash of double could mess up.

  • Use an object as hashmap keys. When the hashCode() and equals(Object o) methods are not overridden by your class, the default implementation is used. The default behavior is to treat all objects as different unless they are the same object. IdentityHashMap always does this by using reference-equality in place of object-equality

Map Interface

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

Methods in Map

  • boolean containsKey(Object key): Returns true if this map contains a mapping for the specified key.

  • boolean containsValue(Object value): Returns true if this map maps one or more keys to the specified value.

  • Set<Map.Entry<K, V>> entrySet(): Returns a Set view of the mappings contained in this map.

  • V get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

  • default V getOrDefault(Object key, V defaultValue): Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

  • boolean isEmpty(): Returns true if this map contains no key-value mappings.

  • Set keySet(): Returns a Set view of the keys contained in this map.

  • V put(K key, V value): Associates the specified value with the specified key in this map (optional operation).

  • void putAll(Map<? extends K,? extends V> m): Copies all of the mappings from the specified map to this map (optional operation).

  • default V putIfAbsent(K key, V value): If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

  • V remove(Object key): Removes the mapping for a key from this map if it is present (optional operation).

  • default boolean remove(Object key, Object value): Removes the entry for the specified key only if it is currently mapped to the specified value.

  • default V replace(K key, V value): Replaces the entry for the specified key only if it is currently mapped to some value.

  • default boolean replace(K key, V oldValue, V newValue): Replaces the entry for the specified key only if currently mapped to the specified value.

  • int size(): Returns the number of key-value mappings in this map.

  • Collection values(): Returns a Collection view of the values contained in this map.

HashTable Class

This class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hash table, the objects used as keys must implement the hashCode method and the equals method.

Generally, the default load factor (.75) offers a good tradeoff between time and space costs.

Note, HashTable is synchronized, while HashMap is not. So it is slower than HashMap.

HashTable Constructor

  • Hashtable(): Constructs a new, empty hashtable with a default initial capacity (11) and load factor (0.75).

  • Hashtable(int initialCapacity): Constructs a new, empty hashtable with the specified initial capacity and default load factor (0.75).

  • Hashtable(int initialCapacity, float loadFactor): Constructs a new, empty hashtable with the specified initial capacity and the specified load factor.

  • Hashtable(Map<? extends K,? extends V> t): Constructs a new hashtable with the same mappings as the given Map.

HashTable<String, Integer> ht1 = new HashTable<>();
HashTable<String, Integer> ht2 = new HashTable<>(100);
HashTable<String, Integer> ht3 = new HashTable<>(100, 0.9);
HashTable<String, Integer> ht4 = new HashTable<>(ht3);

Special Methods in HashTable Class

  • void clear(): Clears this hashtable so that it contains no keys.

  • Enumeration elements(): Returns an enumeration of the values in this hashtable.

  • Enumeration keys(): Returns an enumeration of the keys in this hashtable.

  • protected void rehash(): Increases the capacity of and internally reorganizes this hashtable, in order to accommodate and access its entries more efficiently.

  • String toString(): Returns a string representation of this Hashtable object in the form of a set of entries, enclosed in braces and separated by the ASCII characters ", " (comma and space).

HashMap Class

HashMap is a hash-table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Why HashTable doesn’t allow null and HashMap does? 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.

HashMap Constructor

  • HashMap(): Constructs a new, empty HashMap with a default initial capacity (11) and load factor (0.75).

  • HashMap(int initialCapacity): Constructs a new, empty HashMap with the specified initial capacity and default load factor (0.75).

  • HashMap(int initialCapacity, float loadFactor): Constructs a new, empty HashMap with the specified initial capacity and the specified load factor.

  • HashMap(Map<? extends K,? extends V> t): Constructs a new HashMap with the same mappings as the given Map.

HashMap<String, Integer> map1 = new HashMap<>();
HashMap<String, Integer> map2 = new HashMap<>(100);
HashMap<String, Integer> map3 = new HashMap<>(100, 0.9);
HashMap<String, Integer> map4 = new HashMap<>(map3);

Tree Implementations

Another common approach is to implement an associative array with a self-balancing binary search tree, such as an AVL tree or a red-black tree.

Compared to hash tables, these structures have both advantages and weaknesses. The worst-case performance of self-balancing binary search trees is significantly better than that of a hash table, with a time complexity in the big-O notation of O(log n). This is in contrast to hash tables, whose worst-case performance involves all elements sharing a single bucket, resulting in O(n) time complexity. In addition, and like all binary search trees, self-balancing binary search trees keep their elements in order. Thus, traversing its elements follows the least-to-greatest pattern, whereas traversing a hash table can result in elements being in seemingly random order. However, hash tables have a much better average-case time complexity than self-balancing binary search trees of O(1), and their worst-case performance is highly unlikely when a good hash function is used.

TreeMap Class

A Red-Black tree-based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put, and remove operations.

TreeMap Constructor

  • TreeMap(): Constructs a new, empty tree map, using the natural ordering of its keys.

  • TreeMap(Comparator<? super K> comparator): Constructs a new, empty tree map, ordered according to the given comparator.

  • TreeMap(Map<? extends K,? extends V> m): Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.

  • TreeMap(SortedMap<K,? extends V> m): Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

Methods in TreeMap Class

  • Map.Entry<K, V> ceilingEntry(K key): Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

  • K ceilingKey(K key): Returns the least key greater than or equal to the given key, or null if there is no such key.

  • Comparator<? super K> comparator(): Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.

  • boolean containsKey(Object key): Returns true if this map contains a mapping for the specified key.

  • boolean containsValue(Object value): Returns true if this map maps one or more keys to the specified value.

  • NavigableSet descendingKeySet(): Returns a reverse order NavigableSet view of the keys contained in this map.

  • NavigableMap<K, V> descendingMap(): Returns a reverse order view of the mappings contained in this map.

  • Set<Map.Entry<K, V>> entrySet(): Returns a Set view of the mappings contained in this map.

  • Map.Entry<K, V> firstEntry(): Returns a key-value mapping associated with the least key in this map, or null if the map is empty.

  • K firstKey(): Returns the first (lowest) key currently in this map.

  • Map.Entry<K, V> floorEntry(K key): Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

  • K floorKey(K key): Returns the greatest key less than or equal to the given key, or null if there is no such key.

  • V get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

  • SortedMap<K, V> headMap(K toKey): Returns a view of the portion of this map whose keys are strictly less than toKey.

  • NavigableMap<K, V> headMap(K toKey, boolean inclusive): Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.

  • Map.Entry<K, V> higherEntry(K key): Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

  • K higherKey(K key): Returns the least key strictly greater than the given key, or null if there is no such key.

  • Set keySet(): Returns a Set view of the keys contained in this map.

  • Map.Entry<K, V> lastEntry(): Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

  • K lastKey(): Returns the last (highest) key currently in this map.

  • Map.Entry<K, V> lowerEntry(K key): Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

  • K lowerKey(K key): Returns the greatest key strictly less than the given key, or null if there is no such key.

  • NavigableSet navigableKeySet(): Returns a NavigableSet view of the keys contained in this map.

  • Map.Entry<K, V> pollFirstEntry(): Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.

  • Map.Entry<K, V> pollLastEntry(): Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

  • V put(K key, V value): Associates the specified value with the specified key in this map.

  • void putAll(Map<? extends K,? extends V> map): Copies all of the mappings from the specified map to this map.

  • V remove(Object key): Removes the mapping for this key from this TreeMap if present.

  • V replace(K key, V value): Replaces the entry for the specified key only if it is currently mapped to some value.

  • boolean replace(K key, V oldValue, V newValue): Replaces the entry for the specified key only if currently mapped to the specified value.

  • int size(): Returns the number of key-value mappings in this map.

  • NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): Returns a view of the portion of this map whose keys range from fromKey to toKey.

  • SortedMap<K, V> subMap(K fromKey, K toKey): Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

  • SortedMap<K, V> tailMap(K fromKey): Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

  • NavigableMap<K, V> tailMap(K fromKey, boolean inclusive): Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.

  • Collection values(): Returns a Collection view of the values contained in this map.

References