Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Data Structures - Map ADT

    Uploaded by

    Sergey Shamirian
    The document discusses the Map abstract data type (ADT) and its common implementations. It defines a Map as storing unique keys mapped to values, and describes common Map operations like get, put, remove. Sorted Maps maintain sorted keys, and the document compares implementations like HashMap, LinkedHashMap and TreeMap in the Java Collections Framework.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Data Structures - Map ADT

    Uploaded by

    Sergey Shamirian
    42 views7 pages
    The document discusses the Map abstract data type (ADT) and its common implementations. It defines a Map as storing unique keys mapped to values, and describes common Map operations like get, put, remove. Sorted Maps maintain sorted keys, and the document compares implementations like HashMap, LinkedHashMap and TreeMap in the Java Collections Framework.

    Original Title

    Data Structures - Map ADT_0cceeb2258b48d91c11e97720906659b

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the Map abstract data type (ADT) and its common implementations. It defines a Map as storing unique keys mapped to values, and describes common Map operations like get, put, remove. Sorted Maps maintain sorted keys, and the document compares implementations like HashMap, LinkedHashMap and TreeMap in the Java Collections Framework.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    42 views7 pages

    Data Structures - Map ADT

    Uploaded by

    Sergey Shamirian
    The document discusses the Map abstract data type (ADT) and its common implementations. It defines a Map as storing unique keys mapped to values, and describes common Map operations like get, put, remove. Sorted Maps maintain sorted keys, and the document compares implementations like HashMap, LinkedHashMap and TreeMap in the Java Collections Framework.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 7

    Data Structures

    Map ADT
    What is Map?
    ● A map stores key-value pairs (k; v) called entries, where k is the key and v is
    its corresponding value.
    ● Keys are required to be unique, i.e. multiple entries with the same key are not
    allowed.
    ● An example is a dictionary, where the word is mapped to its definition
    Map ADT
    ● The Map ADT models a collection of key and value (k, v) pairs sorted without any particular order.
    ● The element with value v can be placed into and retrieved from the map only through its key k.
    ● Main methods:
    ○ size() - returns the number of entries in the map
    ○ isEmpty()- returns a boolean indicating whether map is empty
    ○ get(k) - returns the value v associated with key k, if such an entry exists, null otherwise
    ○ put(k, v) - if the map does not have an entry with key equal to k, then adds entry (k; v) and returns null,
    otherwise replaces the existing value of the entry with key equal to k with value equal to v and returns
    the old value
    ○ remove(k) - if the map has entry with key equal to k, that entry is removed and its value is returned,
    otherwise null is returned
    ● Collections:
    ○ keySet() - returns an iterable collection containing all the keys stored in the map
    ○ values() - returns an iterable collection containing all the values of entries stored in the map (with
    repetitions if multiple keys of the map had the same value)
    ○ entrySet() - returns an iterable collection containing all the key-value entries in the map
    Sorted Map ADT
    ● A sorted map is an extension of the standard map, that keeps the map keys sorted and in addition to
    the Map ADT methods supports the following:
    ○ firstEntry() - returns the entry with smallest key or null, if the map is empty
    ○ lastEntry() - returns the entry with largest key or null, if the map is empty
    ○ ceilingEntry(k) - returns the entry with the least key value greater than or equal to k or null, if no such
    entry exists
    ○ floorEntry(k) - returns the entry with the greatest key value less than or equal to k or null, if no such
    entry exists
    ○ lowerEntry(k) - returns the entry with the greatest key value strictly less than k or null, if no such entry
    exists
    ○ higherEntry(k) - returns the entry with the least key value strictly greater than k or null, if no such entry
    exists
    ○ subMap(k1; k2) - returns an iteration of all entries with key greater than or equal to k1, but strictly less
    than k2
    Map Implementations
    ● As the Map ADT is all about storing a collection of (key, value) elements, we
    can use any of the known ADTs to implement it. Particularly Array ADT or
    Linked List ADT or Hash Tables.
    ● Here is an example illustration of Map implementation through Linked List
    ADT:

    ● Sorted Maps are usually implemented as balanced Trees for optimal search,
    while still Array or Linked List implementations are also applicable.
    Java Collections Framework - Map Implementations
    ● HashMap: this implementation uses a hash table as the
    underlying data structure. It implements all of the Map
    operations and allows null values and one null key. Consider
    to use a HashMap when order does not matter and nulls are
    acceptable.
    ● LinkedHashMap: this implementation uses a hash table and
    a linked list as the underlying data structures, thus the order of
    a LinkedHashMap is predictable, with insertion-order as the
    default order. This implementation also allows nulls like
    HashMap. So consider using a LinkedHashMap when you
    want a Map with its key-value pairs are sorted by their
    insertion order.
    ● TreeMap: this implementation uses a tree as the underlying
    data structure. A TreeMap is sorted according to the natural
    ordering of its keys, or by a Comparator provided at creation
    time. This implementation does not allow nulls. So consider
    using a TreeMap when you want a Map sorts its key-value
    pairs by the natural order of the keys (e.g. alphabetic order or
    numeric order), or by a custom order you specify.
    Useful Links
    ● Check out Map Collections Algebra section here -
    https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
    ● JCF HashMap source code -
    https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/j
    ava/util/HashMap.java
    ● Textbook, Chapter 14 (HashMap and HashSet)
    ● Textbook, Chapter 12 (TreeSet and TreeMap)

    You might also like