/* String to Integer Hash Map (hash table, association list, dictionary) 

   This implementation of hash maps uses the "open addressing" method,
   which is also referred to as "closed hashing".  It keeps all keys
   and values inside an array, without using a secondary data structure.
   Hash collisions (two different keys that hashes to the same value) are
   resolved using a rehash function.  This version uses the "linear probing"
   rehash method.  
*/

public class simap // String to Integer Hash Map
{
    protected String[] Keys;
    protected Integer[] Vals;
    protected int valcount = 0; // number of values
    protected int keycount = 0;  // >= valcount
    double maxlf = 0.75;
    double targetlf = 0.25;
    public int size() { return valcount; }

    public simap(int cap)
    {
	if (cap<2) cap =2;
	Keys = new String[cap];
	Vals = new Integer[cap];
    }
    
    public void increasecap()
    {
	int cap= (int)(keycount/targetlf + 0.5);
	simap newmap = new simap(cap);
	for(int i=0;i<Keys.length;i++)
	    if (Vals[i]!=null) newmap.set(Keys[i],Vals[i]);
	Keys = newmap.Keys;
	Vals = newmap.Vals;
	keycount = newmap.keycount;
	valcount = newmap.valcount;
    }					
    protected int hash(String key)
    {
	int ax = 0; // accumulator
	for(int i=0;i<key.length() && i<10;i++) ax += (int)key.charAt(i);
	return ax % Keys.length;
    }// hash function
    protected int rehash(int h0, int collisions)
    {
	return (h0+collisions) % Keys.length;
    }

    public void set(String key, Integer val)
    {
	if (key==null) throw new RuntimeException("invalid key");
	if (keycount*1.0/Keys.length >= maxlf) increasecap(); /////
	int h0 = hash(key);
	int h = h0; // final hash value
	int collisions = 0;
	while (!(Keys[h]==null || (Keys[h].equals(key))))
	       h = rehash(h0,++collisions);
	if (Keys[h]==null)
	    {
		keycount++;
		if (val!=null) valcount++;
		Keys[h]=key;  Vals[h] = val;
	    }
	else // replacing existing value
	    {
		if (Vals[h]==null && val!=null) valcount++;
		else if (Vals[h]!=null && val==null) valcount--;
		Vals[h] = val;
	    }
    }//set

    public void remove(String key) { set(key,null); }

    public Integer get(String key)
    {
	if (key==null) throw new RuntimeException("invalid key");
	int h0 = hash(key);
	int h = h0; // final hash value
	int collisions = 0;
	while (!(Keys[h]==null || (Keys[h].equals(key))))
	       h = rehash(h0,++collisions);
	return Vals[h];
    }//get
    
    public static void main(String[] av)
    {
	// Hash map to record IDs of Hofstra students:
	simap ID = new simap(4); // new map with initial capacity 4
	ID.set("John Flocker",702123412); // insert into map
	ID.set("Jane Grazer",702987623);
	ID.set("John Flocker",702445676); // change map
	ID.remove("Jane Grazer");         // delete from map
	System.out.println(ID.get("John Flocker")); // prints 702445676
	//	System.out.println(ID.get("Jane Grazer")); // prints null
	//	System.out.println(ID.get("Joan Wolf")); // prints null

	ID.set("Mary",702000111);
	ID.set("Larz",702333551);
	ID.set("Narx",702654321);
	ID.remove("Larz");
	ID.set("Narx",702654999);	
	System.out.println( ID.get("Narx") );
	System.out.println( ID.get("Larz") );	
    }//main
}