1 16 17 package org.cojen.util; 18 19 import java.util.AbstractCollection ; 20 import java.util.AbstractMap ; 21 import java.util.AbstractSet ; 22 import java.util.Collection ; 23 import java.util.ConcurrentModificationException ; 24 import java.util.Iterator ; 25 import java.util.Map ; 26 import java.util.NoSuchElementException ; 27 import java.util.Set ; 28 29 import java.io.IOException ; 30 import java.io.Serializable ; 31 32 37 public class IntHashMap extends AbstractMap implements Map , Cloneable , Serializable { 38 41 private transient Entry table[]; 42 43 46 private transient int count; 47 48 54 private int threshold; 55 56 61 private float loadFactor; 62 63 70 private transient int modCount = 0; 71 72 81 public IntHashMap(int initialCapacity, float loadFactor) { 82 if (initialCapacity < 0) { 83 throw new IllegalArgumentException ("Illegal Initial Capacity: "+ 84 initialCapacity); 85 } 86 87 if (loadFactor <= 0) { 88 throw new IllegalArgumentException ("Illegal Load factor: "+ 89 loadFactor); 90 } 91 92 if (initialCapacity==0) { 93 initialCapacity = 1; 94 } 95 96 this.loadFactor = loadFactor; 97 table = new Entry[initialCapacity]; 98 threshold = (int)(initialCapacity * loadFactor); 99 } 100 101 109 public IntHashMap(int initialCapacity) { 110 this(initialCapacity, 0.75f); 111 } 112 113 117 public IntHashMap() { 118 this(101, 0.75f); 119 } 120 121 127 public IntHashMap(Map t) { 128 this(Math.max(2 * t.size(), 11), 0.75f); 129 putAll(t); 130 } 131 132 137 public int size() { 138 return count; 139 } 140 141 146 public boolean isEmpty() { 147 return count == 0; 148 } 149 150 158 public boolean containsValue(Object value) { 159 Entry tab[] = table; 160 161 if (value == null) { 162 for (int i = tab.length ; i-- > 0 ;) { 163 for (Entry e = tab[i] ; e != null ; e = e.next) { 164 if (e.value == null) { 165 return true; 166 } 167 } 168 } 169 } else { 170 for (int i = tab.length ; i-- > 0 ;) { 171 for (Entry e = tab[i] ; e != null ; e = e.next) { 172 if (value.equals(e.value)) { 173 return true; 174 } 175 } 176 } 177 } 178 179 return false; 180 } 181 182 190 public boolean containsKey(Integer key) { 191 return containsKey(key.intValue()); 192 } 193 194 202 public boolean containsKey(int key) { 203 Entry tab[] = table; 204 205 int index = (key & 0x7fffffff) % tab.length; 206 for (Entry e = tab[index]; e != null; e = e.next) { 207 if (e.key == key) { 208 return true; 209 } 210 } 211 212 return false; 213 } 214 215 226 public Object get(Integer key) { 227 return get(key.intValue()); 228 } 229 230 241 public Object get(int key) { 242 Entry tab[] = table; 243 244 int index = (key & 0x7fffffff) % tab.length; 245 for (Entry e = tab[index]; e != null; e = e.next) { 246 if (e.key == key) { 247 return e.value; 248 } 249 } 250 251 return null; 252 } 253 254 259 private void rehash() { 260 int oldCapacity = table.length; 261 Entry oldMap[] = table; 262 263 int newCapacity = oldCapacity * 2 + 1; 264 Entry newMap[] = new Entry[newCapacity]; 265 266 modCount++; 267 threshold = (int)(newCapacity * loadFactor); 268 table = newMap; 269 270 for (int i = oldCapacity ; i-- > 0 ;) { 271 for (Entry old = oldMap[i] ; old != null ; ) { 272 Entry e = old; 273 old = old.next; 274 275 int index = (e.key & 0x7fffffff) % newCapacity; 276 e.next = newMap[index]; 277 newMap[index] = e; 278 } 279 } 280 } 281 282 294 public Object put(Integer key, Object value) { 295 return put(key.intValue(), value); 296 } 297 298 310 public Object put(int key, Object value) { 311 Entry tab[] = table; 313 int index = 0; 314 315 index = (key & 0x7fffffff) % tab.length; 316 for (Entry e = tab[index] ; e != null ; e = e.next) { 317 if (e.key == key) { 318 Object old = e.value; 319 e.value = value; 320 return old; 321 } 322 } 323 324 modCount++; 325 if (count >= threshold) { 326 rehash(); 328 329 tab = table; 330 index = (key & 0x7fffffff) % tab.length; 331 } 332 333 Entry e = new Entry(key, value, tab[index]); 335 tab[index] = e; 336 count++; 337 return null; 338 } 339 340 349 public Object remove(Integer key) { 350 return remove(key.intValue()); 351 } 352 353 362 public Object remove(int key) { 363 Entry tab[] = table; 364 365 int index = (key & 0x7fffffff) % tab.length; 366 367 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { 368 if (e.key == key) { 369 modCount++; 370 if (prev != null) { 371 prev.next = e.next; 372 } else { 373 tab[index] = e.next; 374 } 375 376 count--; 377 Object oldValue = e.value; 378 e.value = null; 379 return oldValue; 380 } 381 } 382 383 return null; 384 } 385 386 389 public void clear() { 390 Entry tab[] = table; 391 modCount++; 392 for (int index = tab.length; --index >= 0; ) { 393 tab[index] = null; 394 } 395 count = 0; 396 } 397 398 404 public Object clone() { 405 try { 406 IntHashMap t = (IntHashMap) super.clone(); 407 t.table = new Entry[table.length]; 408 for (int i = table.length ; i-- > 0 ; ) { 409 t.table[i] = (table[i] != null) ? (Entry) table[i].clone() : null; 410 } 411 t.keySet = null; 412 t.entrySet = null; 413 t.values = null; 414 t.modCount = 0; 415 return t; 416 } catch (CloneNotSupportedException e) { 417 throw new InternalError (); 419 } 420 } 421 422 424 private transient Set keySet = null; 425 private transient Set entrySet = null; 426 private transient Collection values = null; 427 428 439 public Set keySet() { 440 if (keySet == null) { 441 keySet = new AbstractSet () { 442 public Iterator iterator() { 443 return new IntHashIterator(KEYS); 444 } 445 public int size() { 446 return count; 447 } 448 public boolean contains(Object o) { 449 return containsKey(o); 450 } 451 public boolean remove(Object o) { 452 return IntHashMap.this.remove(o) != null; 453 } 454 public void clear() { 455 IntHashMap.this.clear(); 456 } 457 }; 458 } 459 return keySet; 460 } 461 462 473 public Collection values() { 474 if (values==null) { 475 values = new AbstractCollection () { 476 public Iterator iterator() { 477 return (Iterator ) new IntHashIterator(VALUES); 478 } 479 public int size() { 480 return count; 481 } 482 public boolean contains(Object o) { 483 return containsValue(o); 484 } 485 public void clear() { 486 IntHashMap.this.clear(); 487 } 488 }; 489 } 490 return values; 491 } 492 493 505 public Set entrySet() { 506 if (entrySet==null) { 507 entrySet = new AbstractSet () { 508 public Iterator iterator() { 509 return (Iterator ) new IntHashIterator(ENTRIES); 510 } 511 512 public boolean contains(Object o) { 513 if (!(o instanceof Map.Entry )) { 514 return false; 515 } 516 Map.Entry entry = (Map.Entry ) o; 517 Integer key = (Integer ) entry.getKey(); 518 Entry tab[] = table; 519 int hash = (key == null ? 0 : key.hashCode()); 520 int index = (hash & 0x7fffffff) % tab.length; 521 522 for (Entry e = tab[index]; e != null; e = e.next) { 523 if (e.key == hash && e.equals(entry)) { 524 return true; 525 } 526 } 527 return false; 528 } 529 530 public boolean remove(Object o) { 531 if (!(o instanceof Map.Entry )) { 532 return false; 533 } 534 Map.Entry entry = (Map.Entry ) o; 535 Integer key = (Integer ) entry.getKey(); 536 Entry tab[] = table; 537 int hash = (key == null ? 0 : key.hashCode()); 538 int index = (hash & 0x7fffffff) % tab.length; 539 540 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { 541 if (e.key == hash && e.equals(entry)) { 542 modCount++; 543 if (prev != null) { 544 prev.next = e.next; 545 } else { 546 tab[index] = e.next; 547 } 548 549 count--; 550 e.value = null; 551 return true; 552 } 553 } 554 return false; 555 } 556 557 public int size() { 558 return count; 559 } 560 561 public void clear() { 562 IntHashMap.this.clear(); 563 } 564 }; 565 } 566 567 return entrySet; 568 } 569 570 573 private static class Entry implements Map.Entry { 574 int key; 575 Object value; 576 Entry next; 577 private Integer objectKey; 578 579 Entry(int key, Object value, Entry next) { 580 this.key = key; 581 this.value = value; 582 this.next = next; 583 } 584 585 protected Object clone() { 586 return new Entry(key, value, (next == null ? null : (Entry) next.clone())); 587 } 588 589 591 public Object getKey() { 592 return (objectKey != null) ? objectKey : (objectKey = new Integer (key)); 593 } 594 595 public Object getValue() { 596 return value; 597 } 598 599 public Object setValue(Object value) { 600 Object oldValue = this.value; 601 this.value = value; 602 return oldValue; 603 } 604 605 public boolean equals(Object o) { 606 if (!(o instanceof Map.Entry )) { 607 return false; 608 } 609 Map.Entry e = (Map.Entry ) o; 610 611 return (getKey().equals(e.getKey())) && 612 (value==null ? e.getValue()==null : value.equals(e.getValue())); 613 } 614 615 public int hashCode() { 616 return key ^ (value==null ? 0 : value.hashCode()); 617 } 618 619 public String toString() { 620 return String.valueOf(key) + "=" + value; 621 } 622 } 623 624 private static final int KEYS = 0; 626 private static final int VALUES = 1; 627 private static final int ENTRIES = 2; 628 629 private class IntHashIterator implements Iterator { 630 Entry[] table = IntHashMap.this.table; 631 int index = table.length; 632 Entry entry; 633 Entry lastReturned; 634 int type; 635 636 641 private int expectedModCount = modCount; 642 643 IntHashIterator(int type) { 644 this.type = type; 645 } 646 647 public boolean hasNext() { 648 while (entry == null && index > 0) { 649 entry = table[--index]; 650 } 651 652 return entry != null; 653 } 654 655 public Object next() { 656 if (modCount != expectedModCount) { 657 throw new ConcurrentModificationException (); 658 } 659 660 while (entry == null && index > 0) { 661 entry = table[--index]; 662 } 663 664 if (entry != null) { 665 Entry e = lastReturned = entry; 666 entry = e.next; 667 return type == KEYS ? e.getKey() : (type == VALUES ? e.value : e); 668 } 669 throw new NoSuchElementException (); 670 } 671 672 public void remove() { 673 if (lastReturned == null) { 674 throw new IllegalStateException (); 675 } 676 if (modCount != expectedModCount) { 677 throw new ConcurrentModificationException (); 678 } 679 680 Entry[] tab = IntHashMap.this.table; 681 int index = (lastReturned.key & 0x7fffffff) % tab.length; 682 683 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { 684 if (e == lastReturned) { 685 modCount++; 686 expectedModCount++; 687 if (prev == null) { 688 tab[index] = e.next; 689 } else { 690 prev.next = e.next; 691 } 692 count--; 693 lastReturned = null; 694 return; 695 } 696 } 697 throw new ConcurrentModificationException (); 698 } 699 } 700 701 712 private void writeObject(java.io.ObjectOutputStream s) throws IOException { 713 s.defaultWriteObject(); 715 716 s.writeInt(table.length); 718 719 s.writeInt(count); 721 722 for (int index = table.length - 1; index >= 0; index--) { 724 Entry entry = table[index]; 725 726 while (entry != null) { 727 s.writeInt(entry.key); 728 s.writeObject(entry.value); 729 entry = entry.next; 730 } 731 } 732 } 733 734 738 private void readObject(java.io.ObjectInputStream s) 739 throws IOException , ClassNotFoundException 740 { 741 s.defaultReadObject(); 743 744 int numBuckets = s.readInt(); 746 table = new Entry[numBuckets]; 747 748 int size = s.readInt(); 750 751 for (int i=0; i<size; i++) { 753 int key = s.readInt(); 754 Object value = s.readObject(); 755 put(key, value); 756 } 757 } 758 759 int capacity() { 760 return table.length; 761 } 762 763 float loadFactor() { 764 return loadFactor; 765 } 766 } 767 | Popular Tags |