Hash Tables

	linked list, no duplicates	balanced trees (e.g., AVL)
add (insert)	O(n)	O(lg n)
delete (remove)	O(n)	O(lg n)
member (contains)	O(n)	O(lg n)

A Hash Table Signature

signature HASH_TABLE =
sig 
  type key
  type value
  type hashtable

  (* new(n) creates a hash table with n buckets *)
  val new : int -> hashtable

  (* insert(ht,key,value) updates a hash table to contain the
   * mapping from key to value.  If key already is in the hash
   * table then this new value is stored in place of the old one.*)
  val insert : hashtable * key * value -> unit

  (* lookup(ht,key) returns the corresponding SOME value if key is
   * found in the hash table, otherwise NONE *)
  val lookup : hashtable * key -> value option

  (* delete(ht,key) removes the specified key and its value if present
   * otherwise has no effect *)
  val delete : hashtable * key -> unit

  (* The size of a hash table *)
  val size : hashtable -> int
end 

Hash functions

Open Addressing

A Hash Table Implementation

signature STRING_HT = HASH_TABLE
  where type key = string and type value = string


structure StringHT :> STRING_HT =
struct 
  type key = string
  type value = string
  type hashtable = ((key * value) list) array

  (* helper function to hash a string to an int.  hashes to a word using
   * byte shift operations and then converts to an int using the algorithm
   * from SML's hashString structure*)
  fun hash (k: key): int =
    let 
      fun charToWord c = Word.fromInt(Char.ord c)
      fun hashChar (c, h) = Word.<<(h, 0w5) + h + 0w720 + (charToWord c)
    in 
      Int.abs(Word.toIntX(CharVector.foldl hashChar 0w0 k))
    end 

  fun new(n: int): hashtable = Array.array(n,nil)

  (* Helper function to remove an element from a list *)
  fun remove(k: key, l: (key*value) list) = 
     List.filter (fn(k',_) => k' <> k) l

  fun insert(t: hashtable, k: key, v: value): unit =
    let val bucket = Int.mod(hash k, Array.length t)
        val entries = Array.sub(t, bucket)
   in 
     if List.exists(fn (k',_) => k=k') entries 
        then Array.update(t, bucket, (k,v)::remove(k,entries))
        else Array.update(t, bucket, (k,v)::entries)
   end 

  fun lookup(t: hashtable, k: key): value option =
    let val bucket = Int.mod(hash k, Array.length t)
        val entries = Array.sub(t, bucket)
   in 
      List.find (fn (k',_) => k=k') entries
   end 

  fun delete(t: hashtable, k: key): unit =
    let val bucket = Int.mod(hash k, Array.length t)
        val entries = Array.sub(t, bucket)
    in 
      if List.exists(fn (k',_) => k=k') entries then ()
      else Array.update(t, bucket, remove(k,entries))
    end 

   fun size(t: hashtable): int = 
       Array.foldl (fn (x,y) => length(x) + y) 0 ht
end 

Specifying hash functions

Resizable hash tables and amortized analysis

Using references

ML allows you to allocate and manipulate mutable storage cells. Here are a few simple examples:

val r = ref 0    (*create an int cell initialized to 0 *)
val s = ref 0    (*create an int cell initialized to 0 *)   
val _ = r:= 3    (*update value of cell pointed to by r to 3 *)
val x = !s + !r  (*adds values in cells pointed to by s and t*)
val t = r        (*t and r now point to the same cell *)
val _ = t := 5   (*update cell pointed to by t (and r) *)
val y = !s + !t

In the presence of references, the aliasing problem arises: two different "names" for the same storage cell can be created. Aliasing makes it difficult to reason about programs, as shown in the following example:

  fun f (a:int ref, b: int ref) = (a := !a +1;  !b)

  val s = ref 0
  val t = s
  f(s,t)  (*will return 1*)

  

Implementing counters using references

Suppose we want to be able to count how many times a function is invoked in the program.
First attempt: wrap the function to produce another function that increments counter and then calls the function

val counter = ref 0;

fun count f = (counter := !counter +1; f)

val add' = count add;

add' 5 6

!counter (* will return 1 *)

add' 6 7

!counter (* will return 1 *)

Problem: counter is only incremented when we wrap the function. We want it to be incremented whenever we invoke the function.Second attempt:

fun count f = fn x => (counter := !counter +1; f x);

val add' = count add;

add' 4 5;

Problem: this works correctly but we have only one counter for every function we want to wrap.Third attempt:

fun count f =
        let val counter = ref 0
        in  fn x =>  (counter := !counter + 1; f x)            
        end

Problem: counter is not visible to the rest of the program, so we have no way to read counter value when we are done invoking the function!Fourth attempt:

fun count f =
        let val counter = ref 0
        in (fn x => (counter := !counter + 1; f x),
            fn () => !counter)
        end

fun add x y = x + y
val (add', read_counter) = count add
read_counter()
add' 3 4
read_counter()
...  
 

Implementing recursive functions with references

From our previous discussions we know that we can only declare recursive functions using the fun, or val rec statements. We also know that we can use val statements to declare simple (non-recursive) functions. That is, a val declaration of function doesn't allow us to recursively call (or refer to the function) in the declaration. We show the power of references by implementing recursive functions using val statements.
We illustrate our method using the canonical example of recursive functions, the factorial:

fun fact(n: int): int = 
  if n = 0
  then 1
  else n * (fact(n - 1))

If we were to use a val statement to declare fact, the declaration would fail because of the recursive call fact(n - 1). To avoid this problem, we replace the recursive call with a call to a function specified using a reference:

val x: (int -> int) ref = ref (fn _: int => 1)

val fact: int -> int = (fn (n: int) => if n = 0 then 1 else n * (!x)(n - 1))

Function fact does not really implement the factorial yet:

           /
           | 1, if n = 0,
fact(n) = -|
           | n, otherwise.
           \

We can "convince" fact to implement the factorial by resetting reference x to fact itself:

val () = x := fact

With this transformation, we now have a correct implementation of the factorial function:

- fact 0;
val it = 1 : int
- fact 1;
val it = 1 : int
- fact 3;
val it = 6 : int
- fact 10;
val it = 3628800 : int

Bad use of imperative language features

References can be used to implement imperative-style mutable variables, by creating one ref cell per variable. However, writing imperative-style programs in a functional language such as ML represents bad use of the language. The imperative-style factorial function below illustrates the misuse of references:

fun imp_fact (n:int) =
  let
   val result = ref 1
   val i = ref 0
   fun loop () =
      if !i = n then ()
      else (i := !i + 1;
            result := !result * !i;
            loop())
   in  (loop(); !result)
   end

Point: factorial is really a pure function that does not need storage or assignment.