2. HashTables Flashcards
What is a Map in Java?
A Map in Java is a collection that maps keys to values. It is part of the Java Collections Framework and does not allow duplicate keys, but it allows duplicate values.
What are the main interfaces of the Map hierarchy in Java?
The main interfaces of the Map hierarchy in Java are Map, SortedMap, and NavigableMap. Each of these provides different functionalities for storing key-value pairs.
What is the difference between HashMap and TreeMap?
HashMap is an implementation of the Map interface that uses a hash table for storage, providing constant-time performance for basic operations. TreeMap, on the other hand, implements the NavigableMap interface and stores entries in a sorted order based on the natural ordering of the keys or a specified comparator.
What is the purpose of the put() method in a Map?
The put() method is used to add a key-value pair to the Map. If the key already exists, it updates the value associated with that key.
What does the get() method do in a Map?
The get() method retrieves the value associated with a specified key in the Map. If the key is not found, it returns null.
Explain the concept of key uniqueness in Maps.
In a Map, each key must be unique. If a duplicate key is added, the new value will overwrite the existing value associated with that key.
What is the difference between a Map and a Set in Java?
A Map stores key-value pairs, where each key is unique and maps to a specific value. A Set, on the other hand, is a collection that contains no duplicate elements and does not associate any values with its elements.
How does a HashMap handle collisions?
A HashMap handles collisions using a technique called chaining, where each bucket in the hash table contains a linked list of entries. If multiple keys hash to the same bucket, they are stored in the linked list.
What is the initial capacity of a HashMap?
The initial capacity of a HashMap is the number of buckets it uses to store entries. The default initial capacity is 16, and the load factor is 0.75, which determines when to resize the Map.
What is a load factor in the context of HashMap?
The load factor is a measure of how full the HashMap is allowed to get before its capacity is automatically increased. A load factor of 0.75 is commonly used, meaning the Map will resize when it is 75% full.
What is the difference between the keySet() and values() methods in a Map?
The keySet() method returns a Set view of the keys contained in the Map, while the values() method returns a Collection view of the values contained in the Map.
What happens when you call remove() on a Map?
The remove() method removes the key-value pair associated with the specified key from the Map. If the key does not exist, the Map remains unchanged.
What is a LinkedHashMap?
A LinkedHashMap is a HashMap that maintains a linked list of its entries, preserving the order in which they were inserted. This allows for predictable iteration order.
What is the purpose of the entrySet() method in a Map?
The entrySet() method returns a Set view of the mappings contained in the Map, allowing iteration over both keys and values.
True or False: A TreeMap can have null keys.
False. A TreeMap does not allow null keys because it relies on the natural ordering of keys or a comparator.
How can you iterate over a Map in Java?
You can iterate over a Map using a for-each loop with the keySet(), values(), or entrySet() methods. Each method provides a different way to access the keys, values, or both.
What does the containsKey() method do?
The containsKey() method checks if the Map contains a mapping for the specified key. It returns true if the key exists, and false otherwise.
What is the difference between a Map and a ConcurrentMap?
A ConcurrentMap is a specialized Map designed for concurrent access by multiple threads. It provides additional methods for atomic operations and ensures thread safety.
Explain the role of the comparator in a TreeMap.
In a TreeMap, a comparator defines the order of the keys. If no comparator is provided, the keys must implement the Comparable interface to determine their natural order.
What is a default method in the context of the Map interface?
A default method in the Map interface is a method that has a default implementation, which can be overridden by implementing classes. This feature was introduced in Java 8.
What is the purpose of the computeIfAbsent() method in a Map?
The computeIfAbsent() method computes a value for a specified key if it is not already present in the Map, allowing for lazy initialization.
What is the difference between the replace() and put() methods?
The replace() method updates the value for a specified key only if the key is already mapped to a value, while the put() method adds a new key-value pair or updates an existing one regardless of its current state.
Explain the concept of immutability in relation to Maps.
Immutability in the context of Maps refers to the property that once a Map is created, its key-value pairs cannot be modified. Immutable Maps are useful for ensuring that data remains constant throughout the application.
What is the significance of the Map interface in the Java Collections Framework?
The Map interface is significant in the Java Collections Framework because it provides a standard way to represent key-value pairs, allowing developers to use different implementations like HashMap, TreeMap, or LinkedHashMap interchangeably.
What is a WeakHashMap?
A WeakHashMap is a type of Map that uses weak references for its keys. If a key is no longer in ordinary use, it can be garbage collected, allowing for memory-efficient storage.
What does the forEach() method do in a Map?
The forEach() method allows you to iterate over the entries in a Map, applying a specified action to each key-value pair.
How do you create an empty HashMap?
You can create an empty HashMap by using the constructor: HashMap<TypeKey, TypeValue> map = new HashMap<>();
What is the purpose of the merge() method in a Map?
The merge() method combines the value for a key with a new value using a specified remapping function. If the key does not exist, it adds the new key-value pair.
What is the difference between a Map and a MultiMap?
A Map associates a single value with each key, while a MultiMap can associate multiple values with a single key, allowing for a more flexible data structure.
What is a SortedMap?
A SortedMap is a subinterface of Map that maintains its entries in ascending key order. TreeMap is a common implementation of SortedMap.
What are the advantages of using a ConcurrentHashMap?
ConcurrentHashMap offers better performance in concurrent applications by allowing multiple threads to read and write without locking the entire Map, thus improving scalability and reducing contention.
Explain the concept of a mapping in a Map.
A mapping in a Map is the relationship between a key and a value. Each key is associated with exactly one value, and the mapping is what allows for efficient retrieval of values based on their keys.
What is a NavigableMap?
A NavigableMap is a subinterface of SortedMap that provides navigation methods for searching and retrieving keys that are greater than, less than, or equal to a specified key.
What is the use of the replaceAll() method in a Map?
The replaceAll() method updates each entry in the Map by applying a specified remapping function, allowing for bulk updates of values.
How can you convert a Map to a JSON object in Java?
You can convert a Map to a JSON object in Java using libraries like Gson or Jackson, which provide methods to serialize a Map into a JSON format.
What is the purpose of the toString() method in a Map?
The toString() method returns a string representation of the Map, which includes the key-value pairs in the format of [key1=value1, key2=value2, …].
What is the significance of the size() method in a Map?
The size() method returns the number of key-value mappings in the Map, allowing you to determine how many entries are stored.
What is the difference between HashMap and Hashtable?
HashMap is not synchronized and allows null keys and values, while Hashtable is synchronized, does not allow null keys or values, and is considered legacy.
What does the replace(key, value) method do?
The replace(key, value) method replaces the entry for the specified key with the given value if the key is already present in the Map.
What is the purpose of the keySet() method?
The keySet() method provides a Set view of the keys contained in the Map, allowing for operations that involve only the keys.
What is a HashTable in Java?
Hashtable is a synchronized implementation of the Map interface that uses a hash table for storage. It is part of the legacy collection classes and does not allow null keys or values.
True or False: A HashMap is thread-safe.
False. A HashMap is not thread-safe, which means it can lead to inconsistent results when accessed by multiple threads simultaneously.
What does the compute() method do in a Map?
The compute() method computes a new value for a specified key based on its current value and a provided remapping function, allowing for custom updates.
What is the significance of the Map.Entry interface?
The Map.Entry interface represents a key-value pair in a Map. It allows access to both the key and value and is used in methods such as entrySet() for iteration.
How do you check if a Map is empty?
You can check if a Map is empty by using the isEmpty() method, which returns true if the Map contains no key-value mappings.
What is the main advantage of using a TreeMap?
The main advantage of using a TreeMap is that it maintains a sorted order of keys, which allows for efficient range queries and ordered iteration.
What does the values() method return?
The values() method returns a Collection view of the values contained in the Map, allowing for operations that involve only the values.
What is the purpose of the clear() method in a Map?
The clear() method removes all key-value mappings from the Map, effectively emptying it.
Explain the term ‘hash function’ in relation to HashMaps.
A hash function in relation to HashMaps is an algorithm that converts a key into a hash code, which determines the bucket in which the key-value pair will be stored.
What is the role of the rehashing process in HashMap?
Rehashing in HashMap occurs when the number of entries exceeds the product of the load factor and the current capacity, at which point the Map is resized and existing entries are rehashed to new buckets.
What is the significance of the containsValue() method?
The containsValue() method checks if the Map contains at least one mapping for the specified value, returning true if it exists and false otherwise.
How can you make a Map unmodifiable?
You can make a Map unmodifiable by using the Collections.unmodifiableMap() method, which returns a view of the specified Map that does not allow modifications.
What is a properties file in Java?
A properties file in Java is a file that contains key-value pairs, typically used for configuration settings. It can be loaded into a Properties object, which is a subclass of Hashtable.
What does the method getOrDefault() do?
The getOrDefault() method retrieves the value associated with a specified key, or returns a default value if the key is not found in the Map.
What is the primary use case for a ConcurrentSkipListMap?
A ConcurrentSkipListMap is used in concurrent applications where a thread-safe, sorted Map is required, allowing for high concurrency and performance.
What is the purpose of the toArray() method in a Map?
The toArray() method converts the entries of the Map into an array, allowing for easier manipulation and access of the key-value pairs.
How do you create a TreeMap with a custom comparator?
You can create a TreeMap with a custom comparator by passing the comparator as an argument to the constructor: TreeMap<TypeKey, TypeValue> map = new TreeMap<>(comparator);
What is the difference between the Map interface and the AbstractMap class?
The Map interface defines the contract for Map implementations, while the AbstractMap class provides a skeletal implementation that can be extended to create custom Map types.
What is the role of the computeIfPresent() method?
The computeIfPresent() method updates the value for a specified key only if the key is already present in the Map, using a specified remapping function.
What is the main characteristic of a LinkedHashMap?
The main characteristic of a LinkedHashMap is that it maintains the insertion order of its entries, allowing for predictable iteration while still providing efficient access.
What is the purpose of using a Map in Java applications?
Maps are used in Java applications to efficiently store and retrieve data based on unique keys, providing quick access to associated values and enabling various data manipulation tasks.
What is a MultiMap and how does it differ from a regular Map?
A MultiMap is a specialized type of Map that allows multiple values to be associated with a single key, whereas a regular Map can only associate one value with each key.
What is the significance of the default value in a Map?
The default value in a Map is used as a fallback when a specified key does not have an associated value, providing a way to handle missing keys gracefully.
How does the Map interface facilitate data manipulation?
The Map interface provides a set of methods for adding, removing, and updating key-value pairs, as well as for querying the Map’s contents, making data manipulation straightforward and efficient.
What is the difference between a synchronized Map and a concurrent Map?
A synchronized Map is a Map that is synchronized at the method level, ensuring thread safety, while a concurrent Map is designed for high concurrency, allowing multiple threads to read and write simultaneously without blocking.
What is the purpose of the Map.of() method introduced in Java 9?
The Map.of() method is a factory method that creates an immutable Map with a specified number of key-value pairs, providing a convenient way to create small, fixed-size Maps.
What is the main functionality of the Map interface’s subMap() method?
The subMap() method returns a view of the portion of the Map whose keys range from a specified start key to a specified end key, allowing for operations on a subset of entries.
How can you convert a List of entries into a Map?
You can convert a List of entries into a Map using Java Streams by collecting the entries into a Map with a specified key and value extractor.
What are the advantages of using a WeakHashMap?
WeakHashMap allows for automatic memory management by using weak references for keys, making it useful for caching and preventing memory leaks when keys are no longer in use.
What is the significance of the identityHashCode() method when working with Maps?
The identityHashCode() method returns the hash code for a given object based on its reference rather than its value, which can be useful in distinguishing keys that are equal but not identical.
What does the putIfAbsent() method do?
The putIfAbsent() method adds a key-value pair to the Map only if the specified key is not already present, ensuring that no existing value is overwritten.
How does a HashMap ensure that keys are unique?
A HashMap uses the hash code of keys to determine their uniqueness. If two keys have the same hash code, it checks for equality using the equals() method to ensure they are distinct.
What is the main use case for a EnumMap?
An EnumMap is a specialized Map implementation that uses enum types as keys, providing a highly efficient and type-safe way to map enum constants to values.
What is the significance of the Map interface in functional programming?
The Map interface plays a significant role in functional programming by allowing the use of lambda expressions and method references to perform operations on key-value pairs in a declarative manner.
What is the significance of the identity function when using Maps?
The identity function is used in functional programming as a way to return the input value unchanged. It can be useful in Map operations where no transformation is needed.
What is the difference between the Map interface and the HashMap class?
The Map interface defines the contract for key-value pair storage, while the HashMap class provides a concrete implementation of that interface using a hash table for storage.
What does the Map interface’s values() method return?
The values() method returns a Collection view of the values contained in the Map, allowing for operations that involve only the values.
How does the Map interface support functional programming?
The Map interface supports functional programming by allowing the use of lambda expressions and method references to apply operations on key-value pairs, providing a more declarative approach to data manipulation.
What is the role of the Map.Entry interface in a Map?
The Map.Entry interface represents an individual key-value pair in a Map, allowing access to both the key and the value, and is used in methods like entrySet() for iteration.
What is the difference between an ImmutableMap and a regular Map?
An ImmutableMap is a Map that cannot be modified after it is created, whereas a regular Map allows for adding, removing, and updating key-value pairs.
What is a Hashmap?
As we mentioned in the introduction, Hash Table is a data structure which organizes data using hash functions in order to support quick insertion and search.
A data structure used to store information in a table structure with two main components:
Key: Unique identifier
Value: Associated data
Key characteristics:
Uses a hash function to determine data storage location
Provides efficient random access
Allows dynamic resizing
University Student ID Scenario Problem
Front: What challenges exist when using an array to store student IDs?
Array limitations for student ID storage:
Must set size at the start
Inflexible when new students join
Cannot easily expand or contract
Requires predetermining maximum number of students
Linked List Drawbacks
Front: Why is a linked list not ideal for storing student IDs?
Linked list limitations:
Can dynamically resize
Very slow lookup times
Inefficient for large numbers of students
Must traverse entire list to find specific student
Hash Function Mechanics
Front: How does a hash function work in a HashMap?
Hash function process:
Takes a key as input
Generates a unique hash code
Determines storage location for the value
Ensures consistent mapping for identical keys
Enables fast retrieval and storage
Key Selection Warning
Front: What problem can occur if you choose the wrong key in a HashMap?
Poor key selection risks:
Using non-unique identifiers (e.g., student names)
Potential data overwriting
Inability to distinguish between entries
Loss of data integrity
HashMap Core Methods
Front: What are the two primary methods for interacting with a HashMap?
put(): Stores a key-value pair
get(): Retrieves a value using its key
Important considerations:
Cannot use duplicate keys
Must ensure key uniqueness
Provides efficient data access
What makes HashMaps an efficient data structure?
HashMap advantages:
Combines random access of arrays
Supports dynamic resizing like linked lists
Fast retrieval times (O(1) on average)
Flexible key-value storage
Efficient for large datasets
In the university student ID example, how would you use a HashMap?
HashMap Implementation:
Key: Student ID (unique identifier)
Value: Student Name
Example:
What happens if you try to store a value with a key that already exists?
When using an existing key:
The previous value will be overwritten
Only one value can exist per unique key
Ensures data consistency
Requires careful key management
What should you do after understanding HashMap basics?
Next steps in HashMap mastery:
Explore advanced HashMap methods
Understand collision resolution techniques
Learn about different HashMap implementations
Study performance characteristics
Practice implementing in various scenarios
what is the the Principle of Hash Table
The key idea of Hash Table is to use a hash function to map keys to buckets. To be more specific,
When we insert a new key, the hash function will decide which bucket the key should be assigned and the key will be stored in the corresponding bucket;
When we want to search for a key, the hash table will use the same hash function to find the corresponding bucket and search only in the specific bucket.
How does Insertion and searching work with hash maps?
In the example, we use y = x % 5 as our hash function. Let’s go through the insertion and search strategies using this example:
Insertion
we parse the keys through the hash function to map them into the corresponding bucket.
e.g. 1987 is assigned to bucket 2 while 24 is assigned to bucket 4
Search
we parse the keys through the same hash function and search only in the specific bucket.
e.g. if we search for 1987, we will use the same hash function to map 1987 to 2. So we search in bucket 2 and we successfully find out 1987 in that bucket.
e.g. if we search for 23, will map 23 to 3 and search in bucket 3. And We find out that 23 is not in bucket 3 which means 23 is not in the hash table.
