gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/Hash/OHashSet/OHashSet.java b/Hash/OHashSet/OHashSet.java
--- /dev/null
@@ -0,0 +1,185 @@
+/**\r
+ * ADT skup realizovan otvorenih hashovanjem\r
+ * \r
+ * Modifikovana verzija za ilustracije i test program\r
+ */\r
+public class OHashSet<T> implements Set<T> {\r
+\r
+ private static final int DEFAULT_TABLE_SIZE = 101;\r
+\r
+ private static class Node {\r
+ Object value;\r
+ Node next;\r
+\r
+ public Node(Object value) {\r
+ this.value = value;\r
+ }\r
+ }\r
+\r
+ private Node[] table;\r
+\r
+ private int count;\r
+ private int[] tableCount;\r
+\r
+ public OHashSet() {\r
+ this(DEFAULT_TABLE_SIZE);\r
+ }\r
+\r
+ public OHashSet(int size) {\r
+ if (size <= 0)\r
+ throw new IllegalArgumentException(\r
+ "Velicina hash tabele ne moze biti negativna");\r
+\r
+ table = new Node[size];\r
+ tableCount = new int[size];\r
+ count = 0;\r
+ }\r
+\r
+ private int hash(T o) {\r
+ if (o == null)\r
+ throw new IllegalArgumentException(\r
+ "Hash funkcija se ne moze racunati za null objekat");\r
+\r
+ return Math.abs(o.hashCode() % table.length);\r
+ }\r
+\r
+ /**\r
+ * Pretrazuje listu kolizija za datu vrednost hash funkcije (drugi argument\r
+ * metoda) trazeci element (prvi argument metoda).\r
+ * \r
+ * Metod vraca null ukoliko element ne postoji u tabeli, ili niz od dve\r
+ * reference: 1. prva referenca je referenca na trazeni element 2. druga\r
+ * referenca je referenca na element ispred trazenog elementa\r
+ */\r
+ private Node[] searchColissionChain(T element, int hashValue) {\r
+ Node current = table[hashValue];\r
+ Node prev = null;\r
+\r
+ while (current != null) {\r
+ if (current.value.equals(element)) {\r
+ Node[] ret = new Node[2];\r
+ ret[0] = current;\r
+ ret[1] = prev;\r
+ return ret;\r
+ }\r
+\r
+ prev = current;\r
+ current = current.next;\r
+ }\r
+\r
+ return null;\r
+ }\r
+\r
+ public boolean add(T element) {\r
+ int hashValue = hash(element);\r
+ Node[] n = searchColissionChain(element, hashValue);\r
+ if (n != null) {\r
+ return false;\r
+ }\r
+\r
+ Node newElement = new Node(element);\r
+ newElement.next = table[hashValue];\r
+ table[hashValue] = newElement;\r
+\r
+ count++;\r
+ tableCount[hashValue]++;\r
+ return true;\r
+ }\r
+\r
+ public boolean remove(T element) {\r
+ int hashValue = hash(element);\r
+ Node[] n = searchColissionChain(element, hashValue);\r
+ if (n == null)\r
+ return false;\r
+\r
+ if (n[0] == table[hashValue]) {\r
+ table[hashValue] = table[hashValue].next;\r
+ } else {\r
+ n[1].next = n[0].next;\r
+ }\r
+\r
+ count--;\r
+ tableCount[hashValue]--;\r
+ return true;\r
+ }\r
+\r
+ public boolean contains(T element) {\r
+ return searchColissionChain(element, hash(element)) != null;\r
+ }\r
+\r
+ public void print() {\r
+ for (int i = 0; i < table.length; i++) {\r
+ System.out.print("HashCode = " + i + ": ");\r
+\r
+ Node head = table[i];\r
+ if (head == null) {\r
+ System.out.println(" empty");\r
+ } else {\r
+ while (head != null) {\r
+ System.out.print("[" + head.value + "]");\r
+ head = head.next;\r
+ }\r
+ System.out.println();\r
+ }\r
+ }\r
+ }\r
+\r
+ public String toString() {\r
+ return "OHashSet; br elemenata " + getCount();\r
+ }\r
+\r
+ public int getCount() {\r
+ return count;\r
+ }\r
+\r
+ public int size() {\r
+ return getCount();\r
+ }\r
+\r
+ public double getChiSquare() {\r
+ double chi = 0.0;\r
+\r
+ if (count > 0 && table.length > 0) {\r
+ double avg = (double) count / table.length;\r
+ for (int i = 0; i < tableCount.length; i++) {\r
+ chi += (tableCount[i] - avg) * (tableCount[i] - avg) / avg;\r
+ }\r
+ }\r
+ return chi;\r
+ }\r
+\r
+ public double getPercentFull() {\r
+ if (tableCount.length == 0) {\r
+ return 0;\r
+ }\r
+\r
+ int filled = 0;\r
+\r
+ for (int i = 0; i < tableCount.length; i++) {\r
+ if (tableCount[i] > 0)\r
+ filled++;\r
+ }\r
+\r
+ return filled * 100.0 / tableCount.length;\r
+ }\r
+\r
+ public void printStats() {\r
+ System.out.printf("Elements : %3d%n", getCount());\r
+ System.out.printf("Percent full: %6.2f %n", getPercentFull());\r
+ System.out.printf("Chi square : %8.4f %n", getChiSquare());\r
+ System.out.printf("'Columns' : %3d%n", table.length);\r
+ }\r
+\r
+ @SuppressWarnings("unchecked")\r
+ public T someElement() {\r
+ if (count > 0) {\r
+ for (int i = 0; i < table.length; i++) {\r
+ Node head = table[i];\r
+ if (head != null) {\r
+ return (T) head.value;\r
+ }\r
+ }\r
+ }\r
+ return null;\r
+ }\r
+}\r