|
What this is
Other links
The source code/* * Sun Public License Notice * * The contents of this file are subject to the Sun Public License * Version 1.0 (the "License"). You may not use this file except in * compliance with the License. A copy of the License is available at * http://www.sun.com/ * * The Original Code is NetBeans. The Initial Developer of the Original * Code is Sun Microsystems, Inc. Portions Copyright 1997-2004 Sun * Microsystems, Inc. All Rights Reserved. */ package org.netbeans.modules.javacore.scanning; import org.netbeans.modules.javacore.JMManager; /** * Fast set class for ints, loosely based java.util.HashTable, HashSet, * and the discussion of hashtables from "Data Structures & Algorithms * in Java" by Robert Lafore. * * @author Tom Ball */ final class IntSet { static class Entry { int value; int hash; Entry next; Entry(int v, int h, Entry n) { value = v; hash = h; next = n; } } private Entry[] table; private int size; private static final int LOAD_FACTOR = 2; private static final int GROWTH_FACTOR = 2; public IntSet() { // 2048 is the max used by all of the JDK sources. // Use fewer only if the set is referenced longer than // the body of makeIndexes() above. this(2048); } public IntSet(int capacity) { table = new Entry[capacity]; } public boolean add(int x) { if (contains(x)) return false; if (size > table.length / LOAD_FACTOR) resize(); int h = hash(x); int idx = indexFor(h, table.length); Entry e = new Entry(x, h, table[idx]); table[idx] = e; size++; return true; } public boolean contains(int x) { int h = hash(x); Entry e = table[indexFor(h, table.length)]; while (e != null) { if (e.value == x) return true; e = e.next; } return false; } public int[] toArray() { int[] arr = new int[size]; int n = 0; Entry eNext; for (int i = 0; i < table.length; i++) for(Entry e = table[i]; e != null; e = e.next) arr[n++] = e.value; assert n == size; return arr; } private void resize() { Entry[] newt = new Entry[table.length * GROWTH_FACTOR]; Entry eNext; for(int i = 0; i < table.length; i++) for(Entry e = table[i]; e != null; e = eNext) { int idx = indexFor(e.hash, newt.length); eNext = e.next; e.next = newt[idx]; newt[idx] = e; } table = newt; JMManager.getLog().log("IntSet: table doubled to " + table.length); } // hash(), forIndex() from java.util.HashMap /** * Returns a hash value for the specified object. In addition to * the object's own hashCode, this method applies a "supplemental * hash function," which defends against poor quality hash functions. * This is critical because HashMap uses power-of two length * hash tables. |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.