Code&Data Insights
[Data Structure] Map, Dictionary 본문
[Data Structure] Map, Dictionary
paka_corn 2022. 11. 17. 11:21[ MAP ]
- (key-value) entries and key should be unique!
- can store elements in a way that attempts to speed up the process of locating them,
through the utilization of keys
- main operations: search | insert | delete
- methods
: get(k), put(k,v), remove(k), entrySet(), keySet(), values(), size(), isEmpty()
- we can efficiently implement a map using an unsorted list
[ Hash Functions & Hash Table ]
To speed up searching for an entry, we can create an array of holders/ buckets of these entries.
=> hash table
If insertion of entries is made such that each entry can be placed at only one possible location(bucket) in this data structure, then searching for the entry is consequently restricted to searching that particular bucket instead of searching the entire data structure
-> best scenario : searching for entry : O(1)
'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글
[Data Structure] Priority Queue | 우선순위 큐 (0) | 2022.11.13 |
---|---|
[Data Structure] Trees, Binary Trees (2) | 2022.11.08 |
[Data Structure & Algorithm] Time Complexity - O(logn) (1) | 2022.11.08 |
[ Data Structures ]Hash, Hash Table (0) | 2022.11.05 |
[MIT 6.006 - Introduction to Algorithms ] 2. Data Structure and Dynamic Arrays (0) | 2022.01.21 |