Programmazione Parametrica ( a k. a. Generics ) Introduzione ai meccanismi e concetti della programmazione parametrica


Every key in a map has a unique value



Scaricare 446 b.
Pagina17/17
28.03.2019
Dimensione del file446 b.
1   ...   9   10   11   12   13   14   15   16   17

Every key in a map has a unique value

  • A value may be associated with several keys

  • Classes that implement the Map interface

    • HashMap
    • TreeMap


  • An Example of a Map



    Map Classes and Interfaces



    Code for Creating and Using a HashMap

    • //Changing an existing association favoriteColor.put("Juliet",Color.RED);

    • //Removing a key and its associated value favoriteColors.remove("Juliet");



    Code for Creating and Using a HashMap



    Code for Creating and Using a HashMap



    Printing Key/Value Pairs



    File MapTester.java



    File MapTester.java



    File MapTester.java

    • Output



    Self Check

    • What is the difference between a set and a map?

    • Why is the collection of the keys of a map a set?



    Answers

    • A set stores elements. A map stores associations between keys and values.

    • The ordering does not matter, and you cannot have duplicates.



    Hash Tables

    • Hashing can be used to find elements in a data structure quickly without making a linear search

    • A hash table can be used to implement sets and maps

    • A hash function computes an integer value (called the hash code) from an object



    Hash Tables



    Sample Strings and Their Hash Codes



    Simplistic Implementation of a Hash Table

    • To implement

      • Generate hash codes for objects
      • Make an array
      • Insert each object at the location of its hash code
    • To test if an object is contained in the set

      • Compute its hash code
      • Check if the array position with that hash code is already occupied


    Simplistic Implementation of a Hash Table



    Problems with Simplistic Implementation

    • It is not possible to allocate an array that is large enough to hold all possible integer index positions

    • It is possible for two different objects to have the same hash code



    Solutions

    • Pick a reasonable array size and reduce the hash codes to fall inside the array

    • When elements have the same hash code:

      • Use a node sequence to store multiple objects in the same array position
      • These node sequences are called buckets


    Hash Table with Buckets to Store Elements with Same Hash Code



    Algorithm for Finding an Object x in a Hash Table

    • Get the index h into the hash table

    • Iterate through the elements of the bucket at position h

      • For each element of the bucket, check whether it is equal to x
    • If a match is found among the elements of that bucket, then x is in the set

      • Otherwise, x is not in the set


    Hash Tables

    • A hash table can be implemented as an array of buckets

    • Buckets are sequences of nodes that hold elements with the same hash code

    • If there are few collisions, then adding, locating, and removing hash table elements takes constant time

      • Big-Oh notation:    O(1)


    Hash Tables

    • For this algorithm to be effective, the bucket sizes must be small

    • The table size should be a prime number larger than the expected number of elements

      • An excess capacity of 30% is typically recommended


    Hash Tables

    • Adding an element: simple extension of the algorithm for finding an object

      • Compute the hash code to locate the bucket in which the element should be inserted
      • Try finding the object in that bucket
      • If it is already present, do nothing; otherwise, insert it


    Hash Tables

    • Removing an element is equally simple

      • Compute the hash code to locate the bucket in which the element should be inserted
      • Try finding the object in that bucket
      • If it is present, remove it; otherwise, do nothing
    • If there are few collisions, adding or removing takes O(1) time



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File HashSet.java



    File SetTester.java



    File SetTester.java



    File SetTester.java

    • Output



    Self Check

    • If a hash function returns 0 for all values, will the HashSet work correctly?

    • What does the hasNext method of the HashSetIterator do when it has reached the end of a bucket?



    Answers

    • Yes, the hash set will work correctly. All elements will be inserted into a single bucket.

    • It locates the next bucket in the bucket array and points to its first element.





    Condividi con i tuoi amici:
    1   ...   9   10   11   12   13   14   15   16   17


    ©astratto.info 2019
    invia messaggio

        Pagina principale