public class HashTable {

    public static final int CAPACITA = 127;
    private String[] table;

    /**
     * costruisce una tavola vuota
     */
    public HashTable() {
        table = new String[CAPACITA];
    }

	public String toString() {
		String h = "";
        for (int i = 0; i < CAPACITA; i++) {
		    if (table[i] == null)
				continue;
            h += String.format("[K:%8s, PK:%8d, POS:%2d]\n",
 			                    table[i],
								polyHash(table[i]) % CAPACITA,
								i);
        }
		return h;
	}

	/*
	 * Linear probing
	 */
    public int putLP(String key) {
	    int p = 0;
		int i = 0;
		int k = (polyHash(key) % CAPACITA);
        for (; p < CAPACITA; p++)  {
		    i = ((k+p) % CAPACITA);
			if (table[i] == null || table[i].equals(key))
				break;
		}
        if (table[i] != null && !table[i].equals(key)) 
			throw new RuntimeException("Full structure");
		table[i] = key;
		return p;
	}
	
	/*
	 * Quadratic probing
	 */
    public int putQP(String key) {
	    int p = 0;
		int i = 0;
		int k = (polyHash(key) % CAPACITA);
        for (; p < CAPACITA; p++)  {
			i = ((k+(p*p)) % CAPACITA);
			if (table[i] == null || table[i].equals(key))
				break;
		}
        if (table[i] != null && !table[i].equals(key)) 
			throw new RuntimeException("Full structure");
		table[i] = key;
		return p;
	}	
	
	/*
	 * Double hashing
	 */
    public int putDH(String key) {
	    int p = 0;
		int i = 0;
		int k = ( polyHash(key) % CAPACITA);
		int h = (sommaHash(key) % 7) + 1;
        for (; p < CAPACITA; p++)  {
			i = ((k+(p*h)) % CAPACITA);
			if (table[i] == null || table[i].equals(key))
				break;
		}
        if (table[i] != null && !table[i].equals(key)) 
			throw new RuntimeException("Full structure");
		table[i] = key;
		return p;
	}
	
	/*
	 * Hashing Somma
	 */
    private static int sommaHash(String key) {
        int count = 0;
        for (int i = 0; i < key.length(); i++) {
            count += key.charAt(i);
        }
        return count;
    }
	
	/*
	 * Hashing Polinomiale
	 */
    private static int polyHash(String key) {
	    int count   = 0;
        int a       = 7;
        int potenza = 1;
        for (int i = 0; i < key.length(); i++) {
            count += key.charAt(i) * potenza;
            potenza = potenza * a;
        }
        return count;
    }	
}