[PDF] Hash Table an ArrayList based dictionary. One

View - Download Hash Table

Previous PDF

Next PDF

Hash Table Overview

-A map/dictionary can be implemented using Binary Search Tree or ArrayList. -Search in a BST based dictionary is more efficient than an ArrayList based dictionary.

-The time complexity for search is O(log n) in a balanced BST based dictionary and is O(n) in an ArrayList based dictionary.

-Can we do better?

•If we can read the key of an entry as an integer and use that integer as the index into the underlying array, we can get the value of that entry with time complexity O(1).

Hash Function

-The function that converts a value to an index is called a hash function. -A hash function is a function which when given a key, generates an index in the array.

-A hash function that returns a unique hash number is called universal hash function. It is extremely difficult to assign unique hash numbers to objects in practice, unless the number of objects to be processed can be known.

-A hash function has the following properties: •It always returns a number for an object •Two equal objects will always have the same number •Two unequal objects will not always have different number -How to choose a hash function? •One way is to use Java's hashCode() method.

•The hashCode() method is implemented in the Object class and therefore each class in Java inherits it.

•The hash code provides a numeric representation of an object.

Integer i = new Integer(10); String s = new String("10"); System.out.println("integer 10's hash code " + i.hashCode()); System.out.println("string 10's hash code " + s.hashCode()); integer 10's hash code 10 string 10's hash code 1567 Store Objects

-Create an array of size N. Choose a hash function h. Map the objects to the array using the hash function and modulo. Such array is called a hash table.

Implementation

-Implement chaining hash table (open hash table) using ArrayList

/** * Hash table stores pairs * Ying Li * 04/06/2018 */import java.util.ArrayList;public class StrHashTable { private ArrayList>> table; // create a table with the initial capacity public StrHashTable (int initCap) { table = new ArrayList>>(initCap); for (int i = 0; i < initCap; i++) { table.add(new ArrayList>()); } } // add the key value paire into the table, using key to find the appropriate location public void put (String key, Integer value) { int hash = key.hashCode(); int index = hash % table.size(); ArrayList> chain = table.get(index); for (KeyValuePair pair : chain) { if (pair.getKey().equals(key)) { pair.setValue(value); return; } } chain.add(new KeyValuePair(key, value)); } // get the value associated with the given key public Integer get (String key) { int hash = key.hashCode(); int index = hash % table.size(); ArrayList> chain = table.get(index); for (KeyValuePair pair : chain) { if (pair.getKey().equals(key)) { return pair.getValue(); } } return null; } public String toString () { String s = ""; for (ArrayList> chain : table) { for (KeyValuePair pair : chain) { s += pair.toString() + " "; } s += "\n"; } return s; } public static void main (String[] args) {

StrHashTable table = new StrHashTable(10); table.put("A", 1); table.put("B", 2); System.out.println(table); System.out.println("~~~~~~~~~~~~~~~~~~~"); table.put("Aa", 3); table.put("BB", 4); System.out.println(table); System.out.println("~~~~~~~~~~~~~~~~~~~"); table.put("B", 5); System.out.println(table); System.out.println("~~~~~~~~~~~~~~~~~~~"); System.out.println(table.get("Aa")); System.out.println(table.get("AA")); }} REF: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Hashing/hashing.htmlREF: https://algs4.cs.princeton.edu/34hash/Disclaimer: Notes adapted from previous CS 231 lecture materials at Colby College.

quotesdbs_dbs20.pdfusesText_26

[PDF] arraylist length java

[PDF] arraylist object java android

[PDF] arraylist object java sort

[PDF] arraylist object javascript

[PDF] arrays in java

[PDF] arrhenius equation activation energy

[PDF] arrhenius equation derivation

[PDF] arrhenius equation example

[PDF] arrhenius equation graph

[PDF] arrhenius equation ln

[PDF] arrhenius equation pdf

[PDF] arrhenius equation r

[PDF] arrhenius equation units

[PDF] arrima

[PDF] arris vip2262 price