Java Reference
In-Depth Information
Elements in set: [Cook, Anderson, Smith, Lewis]
Number of elements in set: 4
Is Smith in set? true
Names in set in uppercase are COOK ANDERSON LEWIS
Elements in set: []
The program creates a set using MyHashSet (line 4) and adds five elements to the set (lines
5-9). Line 5 adds Smith and line 9 adds Smith again. Since only nonduplicate elements are
stored in the set, Smith appears in the set only once. The set actually has four elements. The
program displays the elements (line 11), gets its size (line 12), checks whether the set contains
a specified element (line 13), and removes an element (line 15). Since the elements in a set
are iterable, a foreach loop is used to traverse all elements in the set (lines 17-18). Finally, the
program clears the set (line 20) and displays an empty set (line 21).
27.26
Why can you use a foreach loop to traverse the elements in a set?
Check
27.27
Describe how the add(e) method is implemented in the MyHashSet class.
Point
27.28
In Listing 27.5, the remove method in the iterator removes the current element from
the set. It also removes the current element from the internal list (line 161):
list.remove(current); // Remove current element from the list
Is this necessary?
27.29
Replace the code in lines 146-149 In Listing 27.5 using one statement.
K EY T ERMS
associative array
986
linear probing 989
load factor 993
open addressing 989
perfect hash function
cluster 990
dictionary 986
double hashing
991
986
hash code 987
hash function
polynomial hash code
988
986
quadratic probing
990
hash map
1004
rehashing 993
secondary clustering
hash set
1004
991
hash table
986
separate chaining
993
C HAPTER S UMMARY
1. A map is a data structure that stores entries. Each entry contains two parts: a key and a
value . The key is also called a search key , which is used to search for the corresponding
value. You can implement a map to obtain O (1) time complexity on searching, retrieval,
insertion, and deletion using the hashing technique.
2. A set is a data structure that stores elements. You can use the hashing technique to imple-
ment a set to achieve O (1) time complexity on searching, insertion, and deletion for a set.
3.
Hashing is a technique that retrieves the value using the index obtained from a key
without performing a search. A typical hash function first converts a search key to
 
 
Search WWH ::




Custom Search