Hash表

key elements: underlying array and a hash function
when you want to insert an object and its key, the hash function maps the key to an integer, which indicates the
index in the array. The object is then stored at that index.

Implementation
one:
extremely large array, the result of the function can not be duplicated. (high space complexity)
search time complexity are: O(1).
two:
the result of the function can be duplicated, then, smaller array, each index points to an linked list.(each
position is hash(key)%array_length)
search time complexity is: O(n/array_length).
three:
using a tree to store the indexes and objects, if it is balanced tree, time complexity is O(logn).

1, use what strategy to implement the hash function?
division, mid-square, folding, digit analysis

2, how to deal with overflow?
open addressing, chaining




package topic_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//Version one: no collision
//public class HashImplementation {
//    private List<Integer> list;
//    private static final int mode=12;
//    HashImplementation(){
//        list=new ArrayList<Integer>(mode);
//        int m=0;
//        while(m<mode){
//            list.add(null);
//            m++;
//        }
//    }
//   
//    public void put(int key){
//        int index=hashFunction(key);
//        list.set(index, key);
//    }
//   
//    public boolean hasKey(int key){
//        int index=hashFunction(key);
//        if(list.get(index)!=null&&list.get(index)==key){
//            return true;
//        }
//        return false;
//    }
//   
//    private int hashFunction(int key){
//        return key%mode;
//    }
//   
//    public int size(){
//        return list.size();
//    }
//}

//Version two: has collision
//solution one: open addressing
//public class HashImplementation {
//    private List<Integer> list;
//    private static final int mode = 12;
//
//    HashImplementation() {
//        list = new ArrayList<Integer>(mode);
//        int m = 0;
//        while (m < mode) {
//            list.add(null);
//            m++;
//        }
//    }
//
//    public void put(int key) {
//        int index = hashFunction(key);
//        while(list.get(index)!=null){
//            //has collision
//            //solution one: open addressing
//            index=hashFunction(index+1);
//           
//        }
//        list.set(index, new Integer(key));
//    }
//
//    public boolean hasKey(int key) {
//        int index = hashFunction(key);
//        while(list.get(index)!=null){
//            if(list.get(index)==key){
//                return true;
//            }
//            index=hashFunction(index+1);
//        }
//        return false;
//    }
//
//    private int hashFunction(int key) {
//        return key % mode;
//    }
//
//    public int size() {
//        return list.size();
//    }
//}

//Version three: has collision
//solution two: chaining
public class HashImplementation {
    private List<LinkedList<Integer>> list;
    private static final int mode = 12;
   
    HashImplementation() {
      list = new ArrayList<LinkedList<Integer>>(mode);
      int m = 0;
      while (m < mode) {
          list.add(null);
          m++;
      }
    }
   
    public void put(int key) {
      int index = hashFunction(key);
      if(list.get(index)==null){
          LinkedList<Integer> llist=new LinkedList<Integer>();
          llist.add(key);
          list.set(index,llist);
      }else{
          LinkedList<Integer> ll=list.get(index);
          ll.offer(key);
      }
    }
   
    public boolean hasKey(int key) {
      int index = hashFunction(key);
      if(list.get(index)==null){
          return false;
      }else{
          LinkedList<Integer> llist=list.get(index);
          for(int i=0;i<llist.size();i++){
              Integer ints=llist.get(i);
              if(key==ints){
                  return true;
              }
          }
          return false;
      }
    }
   
    private int hashFunction(int key) {
      return key % mode;
    }
   
    public int size() {
      return list.size();
    }
}