[Data Structures & Algorithms in Java 6th] Ch.10- Maps

---

Maps - Github 코드

 

- Intro to Maps

 . Retrieve based on keys, which are unique.

 . Similar with arrays in that assists key uses like an index, but it need not be numeric and don't designate directly as array.

 . Have advantage when save data by uninteger index.

   > Applications of Maps are ID-PW, Domain-IP...etc

 

- Ambiguity of null in Maps

  . put returns null if when entry is empty. It can return null also when (k, null) key has value of null.

   > Some implementations explicitly forbid use of null value. However, we can use containsKey(k) to find out whether entry is null.

 

- Implementation of Unsorted Map

 . O(n). Not efficient because of the need of scan through the entire list.

 . put, get, remove methods requires check if value k is empty. Use nonpublic method findIndex(k) for that.

   > In remove, we can use ArrayList class's remove method but we don't because of unnecessary of loop shifts all subsequent to the left. Since map is not unordered, we relocate last entry to vacate(removed) cell, remove last entry.

---

출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition (Michael T. Goodrich, Wiley)