散列集合

Set注重独一无二的性质，该体系集合用于存储无序元素（存入和取出的顺序不一定相同），值不能重复。对象相等性本质是对象hashCode值（java十一局对象的内存地址计算出来的此序号）判断的，如果想要两个不同的对象视为相等的，就必须覆盖Object的hashCode方法和equals方法。

使用散列实现集合

Java集合框架定义了java.util.Set接口来对集合建模。三种具体的实现是HashSet、LinkedHashSet和TreeSet，HashSet采用散列实现，LinkedHashSet采用LinkedList实现，TreeSet采用红黑树实现。

MyMap接口

MySet接口

public interface MySet<E> extends Iterable<E> {

	void clear();

	boolean contains(E e);

	boolean add(E e);

	boolean remove(E e);

	boolean isEmpty();

	int size();
}

MyHashSet实现类

链地址实现MyHashSet

import java.util.LinkedList;

public class MyHashSet<E> implements MySet<E> {
	private static int DEFAULT_INITIAL_CAPACITY = 4;
	private static int MAXIMUM_CAPACITY = 1 << 30;
	private int capacity;
	private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
	private float loadFactorThreshold;
	private int size = 0;
	private LinkedList<E>[] table;

	public MyHashSet() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}

	public MyHashSet(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}

	public MyHashSet(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY)
			this.capacity = MAXIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

		this.loadFactorThreshold = loadFactorThreshold;
		table = new LinkedList[capacity];
	}

	@Override /** Remove all elements from this set */
	public void clear() {
		size = 0;
		removeElements();
	}

	@Override /** Return true if the element is in the set */
	public boolean contains(E e) {
		int bucketIndex = hash(e.hashCode());
		if (table[bucketIndex] != null) {
			LinkedList<E> bucket = table[bucketIndex];
			for (E element : bucket)
				if (element.equals(e))
					return true;
		}

		return false;
	}

	@Override /** Add an element to the set */
	public boolean add(E e) {
		if (contains(e)) // Duplicate element not stored
			return false;

		if (size + 1 > capacity * loadFactorThreshold) {
			if (capacity == MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");

			rehash();
		}

		int bucketIndex = hash(e.hashCode());

		// Create a linked list for the bucket if it is not created
		if (table[bucketIndex] == null) {
			table[bucketIndex] = new LinkedList<E>();
		}
		table[bucketIndex].add(e);
		size++; // Increase size

		return true;
	}

	@Override /** Remove the element from the set */
	public boolean remove(E e) {
		if (!contains(e))
			return false;

		int bucketIndex = hash(e.hashCode());

		// Create a linked list for the bucket if it is not created
		if (table[bucketIndex] != null) {
			LinkedList<E> bucket = table[bucketIndex];
			for (E element : bucket)
				if (e.equals(element)) {
					bucket.remove(element);
					break;
				}
		}
		size--; // Decrease size
		return true;
	}

	@Override /** Return true if the set contains no elements */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** Return the number of elements in the set */
	public int size() {
		return size;
	}

	@Override /** Return an iterator for the elements in this set */
	public java.util.Iterator<E> iterator() {
		return new MyHashSetIterator(this);
	}

	/** Inner class for iterator */
	private class MyHashSetIterator implements java.util.Iterator<E> {
		// Store the elements in a list
		private java.util.ArrayList<E> list;
		private int current = 0; // Point to the current element in list
		private MyHashSet<E> set;

		/** Create a list from the set */
		public MyHashSetIterator(MyHashSet<E> set) {
			this.set = set;
			list = setToList();
		}

		@Override /** Next element for traversing? */
		public boolean hasNext() {
			if (current < list.size())
				return true;

			return false;
		}

		@Override /** Get current element and move cursor to the next */
		public E next() {
			return list.get(current++);
		}

		@Override /** Remove the current element and refresh the list */
		public void remove() {
			// Delete the current element from the hash set
			set.remove(list.get(current));
			list.remove(current); // Remove current element from the list
		}
	}

	/** Hash function */
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}

	/** Ensure the hashing is evenly distributed */
	private static int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}

		return capacity;
	}

	/** Remove all e from each bucket */
	private void removeElements() {
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				table[i].clear();
			}
		}
	}

	/** Rehash the set */
	private void rehash() {
		java.util.ArrayList<E> list = setToList(); // Copy to a list
		capacity <<= 1; // Double capacity
		table = new LinkedList[capacity]; // Create a new hash table
		size = 0; // Reset size

		for (E element : list) {
			add(element); // Add from the old table to the new table
		}
	}

	/** Copy elements in the hash set to an array list */
	private java.util.ArrayList<E> setToList() {
		java.util.ArrayList<E> list = new java.util.ArrayList<>();

		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				for (E e : table[i]) {
					list.add(e);
				}
			}
		}

		return list;
	}

	@Override
	public String toString() {
		java.util.ArrayList<E> list = setToList();
		StringBuilder builder = new StringBuilder("[");

		// Add the elements except the last one to the string builder
		for (int i = 0; i < list.size() - 1; i++) {
			builder.append(list.get(i) + ", ");
		}

		// Add the last element in the list to the string builder
		if (list.size() == 0)
			builder.append("]");
		else
			builder.append(list.get(list.size() - 1) + "]");

		return builder.toString();
	}
}

测试程序

TestMyHashSet.java

public class TestMyHashSet {
	public static void main(String[] args) {
		// Create a MyHashSet
		MySet<String> set = new MyHashSet<>();
		set.add("Smith");
		set.add("Anderson");
		set.add("Lewis");
		set.add("Cook");
		set.add("Smith");

		System.out.println("Elements in set: " + set);
		System.out.println("Number of elements in set: " + set.size());
		System.out.println("Is Smith in set? " + set.contains("Smith"));

		set.remove("Smith");
		System.out.print("Names in set in uppercase are ");
		for (String s : set)
			System.out.print(s.toUpperCase() + " ");

		set.clear();
		System.out.println("\nElements in set: " + set);
	}
}

---