Sets/OOP: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
The Set class should not just blindly use the HashMap, however, as the HashMap allocates space for both keys and values, and all we need to implement a set are the values. | The Set class should not just blindly use the HashMap, however, as the HashMap allocates space for both keys and values, and all we need to implement a set are the values. | ||
As in mathematics, the Set type can be thought of as an elemental building block of more complex objects. For example, | As in mathematics, the Set type can be thought of as an elemental building block of more complex objects. For example, @phishman3579 on github implemented several data structures in Java (Link: https://github.com/phishman3579/java-algorithms-implementation), but one he did not implement was the Set type. Instead, his library relies on the Java API's HashSet, TreeSet, and AbstractSet classes. | ||
Latest revision as of 13:42, 10 September 2017
Sets can utilize many of the same OOP features during implementation that Maps do (see Maps/OOP).
However, one important feature is that sets can be implemented using nothing more than a hash table or hash map, where the value itself is its own key. This enables the definition of a Set class, whose interface may be entirely different from a map or a hash table, but which nevertheless utilizes these data structures under the hood.
The Set class should not just blindly use the HashMap, however, as the HashMap allocates space for both keys and values, and all we need to implement a set are the values.
As in mathematics, the Set type can be thought of as an elemental building block of more complex objects. For example, @phishman3579 on github implemented several data structures in Java (Link: https://github.com/phishman3579/java-algorithms-implementation), but one he did not implement was the Set type. Instead, his library relies on the Java API's HashSet, TreeSet, and AbstractSet classes.
 |
Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
|