Hash/OHashSet.java

   1 /**
   2  * ADT skup realizovan otvorenih hashovanjem
   3  *
   4  * Modifikovana verzija za ilustracije i test program
   5  */
   6 public class OHashSet<T> implements Set<T> {
   7
   8         private static final int DEFAULT_TABLE_SIZE = 101;
   9
  10         private static class Node {
  11                 Object value;
  12                 Node next;
  13
  14                 public Node(Object value) {
  15                         this.value = value;
  16                 }
  17         }
  18
  19         private Node[] table;
  20
  21         private int count;
  22         private int[] tableCount;
  23
  24         public OHashSet() {
  25                 this(DEFAULT_TABLE_SIZE);
  26         }
  27
  28         public OHashSet(int size) {
  29                 if (size <= 0)
  30                         throw new IllegalArgumentException(
  31                                         "Velicina hash tabele ne moze biti negativna");
  32
  33                 table = new Node[size];
  34                 tableCount = new int[size];
  35                 count = 0;
  36         }
  37
  38         private int hash(T o) {
  39                 if (o == null)
  40                         throw new IllegalArgumentException(
  41                                         "Hash funkcija se ne moze racunati za null objekat");
  42
  43                 return Math.abs(o.hashCode() % table.length);
  44         }
  45
  46         /**
  47          * Pretrazuje listu kolizija za datu vrednost hash funkcije (drugi argument
  48          * metoda) trazeci element (prvi argument metoda).
  49          *
  50          * Metod vraca null ukoliko element ne postoji u tabeli, ili niz od dve
  51          * reference: 1. prva referenca je referenca na trazeni element 2. druga
  52          * referenca je referenca na element ispred trazenog elementa
  53          */
  54         private Node[] searchColissionChain(T element, int hashValue) {
  55                 Node current = table[hashValue];
  56                 Node prev = null;
  57
  58                 while (current != null) {
  59                         if (current.value.equals(element)) {
  60                                 Node[] ret = new Node[2];
  61                                 ret[0] = current;
  62                                 ret[1] = prev;
  63                                 return ret;
  64                         }
  65
  66                         prev = current;
  67                         current = current.next;
  68                 }
  69
  70                 return null;
  71         }
  72
  73         public boolean add(T element) {
  74                 int hashValue = hash(element);
  75                 Node[] n = searchColissionChain(element, hashValue);
  76                 if (n != null) {
  77                         return false;
  78                 }
  79
  80                 Node newElement = new Node(element);
  81                 newElement.next = table[hashValue];
  82                 table[hashValue] = newElement;
  83
  84                 count++;
  85                 tableCount[hashValue]++;
  86                 return true;
  87         }
  88
  89         public boolean remove(T element) {
  90                 int hashValue = hash(element);
  91                 Node[] n = searchColissionChain(element, hashValue);
  92                 if (n == null)
  93                         return false;
  94
  95                 if (n[0] == table[hashValue]) {
  96                         table[hashValue] = table[hashValue].next;
  97                 } else {
  98                         n[1].next = n[0].next;
  99                 }
 100
 101                 count--;
 102                 tableCount[hashValue]--;
 103                 return true;
 104         }
 105
 106         public boolean contains(T element) {
 107                 return searchColissionChain(element, hash(element)) != null;
 108         }
 109
 110         public void print() {
 111                 for (int i = 0; i < table.length; i++) {
 112                         System.out.print("HashCode = " + i + ": ");
 113
 114                         Node head = table[i];
 115                         if (head == null) {
 116                                 System.out.println(" empty");
 117                         } else {
 118                                 while (head != null) {
 119                                         System.out.print("[" + head.value + "]");
 120                                         head = head.next;
 121                                 }
 122                                 System.out.println();
 123                         }
 124                 }
 125         }
 126
 127         public String toString() {
 128                 return "OHashSet; br elemenata " + getCount();
 129         }
 130
 131         public int getCount() {
 132                 return count;
 133         }
 134
 135         public int size() {
 136                 return getCount();
 137         }
 138
 139         public double getChiSquare() {
 140                 double chi = 0.0;
 141
 142                 if (count > 0 && table.length > 0) {
 143                         double avg = (double) count / table.length;
 144                         for (int i = 0; i < tableCount.length; i++) {
 145                                 chi += (tableCount[i] - avg) * (tableCount[i] - avg) / avg;
 146                         }
 147                 }
 148                 return chi;
 149         }
 150
 151         public double getPercentFull() {
 152                 if (tableCount.length == 0) {
 153                         return 0;
 154                 }
 155
 156                 int filled = 0;
 157
 158                 for (int i = 0; i < tableCount.length; i++) {
 159                         if (tableCount[i] > 0)
 160                                 filled++;
 161                 }
 162
 163                 return filled * 100.0 / tableCount.length;
 164         }
 165
 166         public void printStats() {
 167                 System.out.printf("Elements    : %3d%n", getCount());
 168                 System.out.printf("Percent full: %6.2f %n", getPercentFull());
 169                 System.out.printf("Chi square  : %8.4f %n", getChiSquare());
 170                 System.out.printf("'Columns'   : %3d%n", table.length);
 171         }
 172
 173         @SuppressWarnings("unchecked")
 174         public T someElement() {
 175                 if (count > 0) {
 176                         for (int i = 0; i < table.length; i++) {
 177                                 Node head = table[i];
 178                                 if (head != null) {
 179                                         return (T) head.value;
 180                                 }
 181                         }
 182                 }
 183                 return null;
 184         }
 185 }