对构建hashSet集合的几点见解

[size=medium][/size][color=blue][/color]
最近自己做了一类似于hashSet集合的小程序。该程序通过模仿法hashSet特征，同时也根据自己的一些需要自定义了一些格式内容放里面，实现了add()、search()、remove()等方法。好啦 ！废话就少说啦，下面是我对hashSet的一些总结。欢迎各位大侠指点。。。

1.??? HashSet概述：
?? HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。
?
2.??? HashSet的实现：
?? 对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成， HashSet的源代码如下：
Java代码?
?public class HashSet<E>??
???? extends AbstractSet<E>??
???? implements Set<E>, Cloneable, java.io.Serializable??
?{??
???? static final long serialVersionUID = -5024744406713321676L;??
??
???? // 底层使用HashMap来保存HashSet中所有元素。??
???? private transient HashMap<E,Object> map;??
???????
???? // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。??
???? private static final Object PRESENT = new Object();??
??
???? /**?
????? * 默认的无参构造器，构造一个空的HashSet。?
????? *??
????? * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。?
????? */?
???? public HashSet() {??
???? map = new HashMap<E,Object>();??
???? }??
??
???? /**?
????? * 构造一个包含指定collection中的元素的新set。?
????? *?
????? * 实际底层使用默认的加载因子0.75和足以包含指定?
????? * collection中所有元素的初始容量来创建一个HashMap。?
????? * @param c 其中的元素将存放在此set中的collection。?
????? */?
???? public HashSet(Collection<? extends E> c) {??
???? map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));??
???? addAll(c);??
???? }??
??
???? /**?
????? * 以指定的initialCapacity和loadFactor构造一个空的HashSet。?
????? *?
????? * 实际底层以相应的参数构造一个空的HashMap。?
????? * @param initialCapacity 初始容量。?
????? * @param loadFactor 加载因子。?
????? */?
???? public HashSet(int initialCapacity, float loadFactor) {??
???? map = new HashMap<E,Object>(initialCapacity, loadFactor);??
???? }??
??
???? /**?
????? * 以指定的initialCapacity构造一个空的HashSet。?
????? *?
????? * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。?
????? * @param initialCapacity 初始容量。?
????? */?
???? public HashSet(int initialCapacity) {??
???? map = new HashMap<E,Object>(initialCapacity);??
???? }??
??
3.以上是我参考了hashSet 源代码再结合自己的一些经验给出的几点看法。下面是我这次对hashSet的亲身体验：
/**
?* 主类? 用来处理各种哈希事件
?* @author
?*
?*/
public class HashMain {
?//定义一个具有初始长度的数组
?private? InfoNode[]? nodeArray = new InfoNode[300];
?public static int sum = 100;
?/**
? *? add（）方法? 添加用户
? */
?public void add(int i ,InfoNode node){
??int index = hashFuction(i);
??if(nodeArray[index]==null){//如果该索引位置的数组值为空
???nodeArray[index]=node;
??}else{
???InfoNode root = nodeArray[index];//根节点
???InfoNode next = root.getChild();//此时根节点的下一个节点
???root.setChildNode(node);//设置当前节点为子节点
???node.setFatherNode(root);
???if(next!=null){
????//root.getChild().setChildNode(next);
????node.setChildNode(next);
????next.setFatherNode(node);
???}
??}
?}
?/**
? * 定义一个查找用户的方法（根据用户名字）
? */
?public UserInfo search(String name){
??for(int i=0;i<nodeArray.length;i++){
???InfoNode root = nodeArray[i];
???if(root==null) continue;//如果该数组元素为空 则直接进入下一个循环
???while(root!=null){
????if(root.getInfo().getName().equals(name)){
?????return root.getInfo();
????}
????root = root.getChild();
???}

??}
??return null;
?}
?/**
? * 重载一个查找用户的方法（根据编号）
? */
?public UserInfo search(int number){
??int index = hashFuction(number);//获得该元素在数组中的索引
??InfoNode root = nodeArray[index];
??while(root!=null){
???if(root.getInfo().getNum()==number){
????return root.getInfo();
???}
??}
??return null;
?}
?/**
? * 定义删除某一个用户的方法(根据该用户的名字)
? */
?public void remove(String name){
??for(int i=0;i<nodeArray.length;i++){
???InfoNode root = nodeArray[i];
???if(root==null) continue;//如果数组元素为空 则直接进行下一次循环
???//如果数组本省的元素就是要找的用户的话
???if(root.getInfo().getName().equals(name)){
????InfoNode next = root.getChild();
????if(next!=null){
?????nodeArray[i]=next;
?????System.out.println("删除了名为"+name+"的学生，该学生人气指数为："+root.getInfo().getNum());
?????break;
????}else{
?????nodeArray[i]=null;
?????System.out.println("删除了名为"+name+"的学生，该学生人气指数为："+root.getInfo().getNum());
?????break;
????}
???}
???//遍历整个数组以及数组中原所包含的所有节点
???while(root!=null){
????String userName = root.getInfo().getName();
????if(userName.equals(name)){
?????InfoNode child = root.getChild();
?????InfoNode father = root.getFather();
?????if(child!=null){//如果当前root不是最后一个节点
??????father.setChildNode(child);
??????child.setFatherNode(father);
?????}else{//如果当前root是链表末尾节点
??????father.setChildNode(null);
?????}
?????System.out.println("删除了名为"+name+"的学生，该学生人气指数为："+root.getInfo().getNum());
?????break;
????}
????root = root.getChild();
???}
??}
?}
?/**
? * 哈希函数
? */
?public int hashFuction(int i){
??int index = i%(nodeArray.length-1);
??return index;

?}
?/**
? * 定义重建哈希集合的方法
? */
?public void reSetHash(){
??InfoNode[] reNodeArray = new InfoNode[sum];
??nodeArray = reNodeArray;//，新建一个数组指向原来的数组
??init();
?}
?/**
? * 打印数组的方法
? */
?public int printArray(){
??int count1=0;
??int count2=0;
??for(int i=0;i<nodeArray.length;i++){
???InfoNode nextNode = nodeArray[i];
???//遍历整个数组以及数组中原所包含的所有节点
???while(nextNode!=null){
????String name = nextNode.getInfo().getName();
????int number = nextNode.getInfo().getNum();
????System.out.println(name+"的人气指数是："+number);
????nextNode = nextNode.getChild();
????count1++;
???}
???//遍历数组本身的元素
???if(nodeArray[i]!=null){
????count2++;
???}?
??}
??return count1-count2;//返回幅值
?}
?/**
? * 初始化数组
? * @param userArray
? */
?public void init(){
??for(int i=0;i<sum;i++){//循环创建用户对象
???int number = (int)(Math.random()*400);//产生随机数
???String name = "学生"+String.valueOf(i);
???UserInfo user = new UserInfo(number,name);
???InfoNode node = new InfoNode(user);
???add(number,node);//向数组中添加元素
??}

?}
?/**
? * 主类
? * @param args
? */
?public static void main(String[] args) {
??HashMain hash = new HashMain();
??hash.init();
??//***********************建立hash集合
??int count = hash.printArray();
??System.out.println("幅值为"+count);
??
??//***********************删除某个元素
??hash.remove("学生49");
??
??//***********************根据用户名查找某个元素(遍历查找)
??int time = (int) System.currentTimeMillis();
??UserInfo user = hash.search("学生56");
??int last = ((int) System.currentTimeMillis()-time)*1000;
??if(user!=null){
??System.out.println("查找到了"+user.getName()+"该学生的人气指数是："+user.getNum()+"用时"+last);
??}else{
???System.out.println("该hash集合中没有要查找的元素！");
??}
??
??//***********************根据编号查找某个元素(索引查找)
??int time2 = (int) System.currentTimeMillis();
??UserInfo user2 = hash.search(278);
??int last2 = ((int) System.currentTimeMillis()-time2)*1000;
??if(user2!=null){
??System.out.println("查找到了"+user2.getName()+"该学生的人气指数是："+user2.getNum()+"用时"+last2);
??}else{
???System.out.println("该hash集合中没有要查找的元素！");
??}
??
??//如果链表元素的数目太多则重建hash
??if(count>sum*(1.25)){
???hash.reSetHash();
???System.out.println("重建了hash集合！！！");
??}
?}
}

这是hashSet的主类，这段代码里面还包含大家最熟悉的InfoNode(用户节点类)，以及UserInfo（用户类，即用户节点类的数据域），在这里就不再罗嗦了 :) 。

?

???