SmartHashSet只是为了解释HashSet的原理

写该类的目的只是为了解释下HashSet的大致实现原理，主要要说明的思想是如何解决哈希冲突，在这里使用的是链表来解决哈希冲突。暂时未支持泛型^_^

 

 

一、首先给出实现的原理图

 

     

 

      一行可以看做一个链表，而第一列的所有Node节点是由Node[] nodes数组构成Node节点用于存放集合的数据，这个图不太科学，其实第一列的结点间不应该有箭头，因为是数组么，而不是链表，说明一下哈，以及寻找下一节点，在这里作为SmartHashSet的内部类使用

      Node定义如下：

 

private static class Node {
		/** 每个集合中元素的值 */
		private Object value;
		/** 链表中当前的节点的下一个节点 */
		private Node next;

		public Node(Object value) {
			this.value = value;
		}

		public Object getValue() {
			return value;
		}

		public void setValue(Object value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
	}

 

    二、完整的代码

   

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Collection;

/**
 * 无聊时写的，用于解释HashSet的原理，处理哈西冲突的方法为链表来解决 暂时未引入泛型
 * 
 * @author jaychang
 * 
 */
public class SmartHashSet implements Iterator, Iterable {
	/** 当前集合的大小 */
	private int size = 0;
	/** 这个叫法其实不好，这里的capacity还是不要解释为容量，容量可以无限大，这里该解释为数组大小 */
	private int capacity = 16;
	/** 用于迭代该集合时用到 */
	private int currentIndex = 0;
	/** 节点数组 */
	private Node[] nodes;
	/** 迭代时用到的，为该集合中的所有元素 */
	private Object[] objs;

	/** SmartHashSet内部类，用于存放元素值，以及构成实现SmarjtHashSet的数据结构 */
	private static class Node {
		/** 每个集合中元素的值 */
		private Object value;
		/** 链表中当前的节点的下一个节点 */
		private Node next;

		public Node(Object value) {
			this.value = value;
		}

		public Object getValue() {
			return value;
		}

		public void setValue(Object value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
	}

	/**
	 * 默认构造,初始容量为16
	 */
	public SmartHashSet() {
		super();
		this.nodes = new Node[capacity];
	}

	/**
	 * 定义初始容量的构造
	 * 
	 * @param initialCapacity
	 */
	public SmartHashSet(int initialCapacity) {
		super();
		this.capacity = initialCapacity;
		this.nodes = new Node[initialCapacity];
	}

	/**
	 * 将集合中的所有元素加入该SmartHashSet对象中
	 * 
	 * @param c
	 *            Collection集合接口
	 * @return 只要有一个元素加入不成功，那么就返回false,只有所有元素都加入成功才返回true;
	 */
	public boolean addAll(Collection c) {
		Object[] values = c.toArray();
		for (int i = 0; i < values.length; i++) {
			if (!add(values[i])) {
				for (int j = 0; j < i; j++) {
					remove(values[j]);
				}
			}
			return false;
		}
		return true;
	}

	/**
	 * 删除所有元素
	 * 
	 * @param c
	 *            Collection集合接口
	 * @return 只要有一个元素加入不成功，就返回false,所有元素都删除成功了,则返回true
	 */
	public boolean removeAll(Collection c) {
		Object[] values = c.toArray();
		for (int i = 0; i < values.length; i++) {
			if (!remove(values[i])) {
				for (int j = 0; j < i; j++) {
					add(values[i]);
				}
				return false;
			}
		}
		return true;
	}

	/**
	 * 向SmartHashSet对象中添加一个元素
	 * 
	 * @param o
	 *            要添加的元素
	 * @return 如果集合中不存在该元素，就添加成功，并返回true,否则返回false
	 */
	public boolean add(Object o) {
		// 得到对象o哈希值所对应的索引值
		int index = o.hashCode() % capacity;
		Node pNode = nodes[index];
		// 该数组的这一索引处无元素，则将o加入到该处
		if (pNode == null) {
			nodes[index] = new Node(o);
			size++;
			return true;
			// 如果该索引处的元素，与o相同，则不能加入
		} else {
			Node nextNode = null;
			while (!pNode.equals(o) && (nextNode = pNode.getNext()) != null) {
				pNode = nextNode;
			}
			// 如果pNode.equals(o)为true,那么nextNode必定为null,即已经到了链表尾
			if (!pNode.getValue().equals(o)) {
				// 将元素加入到链表尾部
				pNode.setNext(new Node(o));
				size++;
				return true;
			}
		}
		return false;
	}

	/**
	 * 从该SmartHashSet中删除一个元素才
	 * 
	 * @param o
	 *            要删除的元素值
	 * @return 如果要删除的元素在该SmartHashSet集合中存在，删除成功，返回true,否则返回false
	 */
	public boolean remove(Object o) {
		for (int i = 0; i < capacity; i++) {
			Node prevNode = nodes[i];
			if (prevNode != null && !prevNode.getValue().equals(o)) {
				Node pNode = null;
				// 寻找pNode节点，该节点的值具有与o相同
				while ((pNode = prevNode.getNext()) != null
						&& !pNode.getValue().equals(o)) {
					prevNode = pNode;
				}
				if (pNode != null) {
					prevNode = pNode.getNext();
					// 删除pNode节点
					pNode = null;
					size--;
					return true;
				}
			} else if (prevNode == null) {
				continue;
			} else {
				nodes[i] = null;
				size--;
				return true;
			}
		}
		return false;
	}

	/**
	 * 判断该SmartHashSet中是否存在指定的元素
	 * 
	 * @param o
	 *            指定的元素
	 * @return 如果指定的元素在该SmartHashSet中存在则返回true,否则返回false
	 */
	public boolean contains(Object o) {
		for (int i = 0; i < capacity; i++) {
			Node pNode = nodes[i];
			while (pNode != null) {
				if (pNode.getValue().equals(o)) {
					return true;
				}
				pNode = pNode.next;
			}
		}
		return false;
	}

	/**
	 * 判断该SmartHashSet中是否无元素
	 * 
	 * @return 如果没有元素则返回true,否则返回false
	 */
	public boolean isEmpty() {
		return size == 0 ? true : false;
	}

	/**
	 * 获取集合的大小，即集合中的元素个数
	 * 
	 * @return 集合中元素个数
	 */
	public int size() {
		return size;
	}

	/**
	 * 将集合中的元素以数据的形式返回
	 * 
	 * @return Object数组
	 */
	public Object[] toArray() {
		Object[] values = new Object[size];
		int count = 0;
		for (int i = 0; i < capacity; i++) {
			if (nodes[i] != null) {
				Node p = nodes[i];
				while (p != null) {
					values[count++] = p.getValue();
					p = p.next;
				}
			}
		}
		return values;
	}

	/**
	 * 判断是否还有元素
	 * 
	 * @return 如果还有元素则返回true,否则返回false
	 */
	public boolean hasNext() {
		return currentIndex < size ? true : false;
	}

	/**
	 * 获取迭代的下一个元素
	 * 
	 * @return 下一个元素
	 */
	public Object next() {
		return this.objs[currentIndex++];
	}

	/**
	 * 将当前迭代到的元素从SmartHashSet对象中删除
	 */
	public void remove() {
		remove(this.objs[currentIndex]);
	}

	/**
	 * 清除所有元素
	 */
	public void clear() {
		this.nodes = null;
		this.nodes = new Node[capacity];
		this.size = 0;
		this.currentIndex = 0;
		this.objs = null;

	}

	/**
	 * 仅保留 set 中那些包含在指定 collection 中的元素（可选操作）。 换句话说，移除此 set 中所有未包含在指定 collection
	 * 中的元素。 如果指定的 collection 也是一个 set，则此操作会实际修改此 set，这样其值是两个 set 的一个交集。
	 * 
	 * @param c
	 *            Collection集合
	 * @return 如果此 set 由于调用而发生更改，则返回 true，否则返回false
	 */
	public boolean retainAll(Collection c) {
		int curSize = size;
		Object[] retainObjs = c.toArray();
		Object[] allObjs = toArray();
		int[] indexNeedNotBeDel = new int[allObjs.length];
		Arrays.fill(indexNeedNotBeDel, -1);
		for (int i = 0; i < retainObjs.length; i++) {
			for (int j = 0; j < allObjs.length; j++) {
				if (retainObjs[i].equals(allObjs[j])) {
					indexNeedNotBeDel[j] = 1;
				}
			}
		}
		for (int k = 0; k < allObjs.length; k++) {
			if (indexNeedNotBeDel[k] == -1) {
				remove(allObjs[k]);
			}
		}
		return curSize > size ? true : false;
	}

	/**
	 * 是否包含所有元素
	 * 
	 * @param c
	 *            Collection集合
	 * @return 只有当所有c集合中的所有元素都在SmartHashSet中存在时，才返回true,否则返回false
	 */
	public boolean containsAll(Collection c) {
		Object[] objs = c.toArray();
		for (int i = 0; i < objs.length; i++) {
			if (!contains(objs[i]))
				return false;
		}
		return true;
	}

	/**
	 * 获得SmartHashSet对象的迭代器
	 * 
	 * @return 迭代器
	 */
	public Iterator iterator() {
		this.objs = toArray();
		this.currentIndex = 0;
		return this;
	}

	public String toString() {

		Object[] allObjs = toArray();
		if (allObjs == null)
			return "[  ]";
		StringBuilder buf = new StringBuilder();
		buf.append("[ ");
		for (int i = 0; i < allObjs.length; i++) {

			buf.append(i == 0 ? " [ " : " , [ ");
			buf.append(allObjs[i].toString());
			buf.append(" ] ");
		}
		buf.append(" ]");
		return buf.toString();
	}
}

   下面详细讲一下，SmartHashSet的工作原理，当一个元素加入到集合中时，先调用该集合的hashCode()方法，根据该hashCode()在经过一定的算法(这里我简单的使用o.hashCode() % capacity来得到该元素应该存放在Node[] nodes数组的索引位置)，如果该位置没有元素，即链表的表头为null，那么直接将元素加入。否则就顺序遍历链表，当链表某个结点的值与元素值相同，则本次添加元素操作不成功，如果直到链表末尾都没有与元素值相同的结点，那么将元素加入到此nodes[index]作为表头的链表末尾处。