数据结构——采用分离链接解决冲突问题的散列表(SeparateChainingHashTable)的实现

发表于   |   分类于 ，   |     |   阅读次数

散列表是一种通过元素（关键值）的散列码直接进行数据存取操作的数据结构。
散列码是通过散列函数获取的，一般好的散列函数很重要，可以把元素均匀的散列到数据表中，将有利于数据的存取操作。但是物理空间毕竟是有限的，所以会有不同的元素被散列到同一个位置，这是就涉及到了冲突的问题。这次的数据结构采用的则是分离链接的方式来解决冲突的问题的：具有相同散列码的元素存储在散列码对应的位置的链表中。

变量

  1. private List[] theLists; //链表头的数组
  2. private int currentSize; //散列表中的元素个数
  3. private static int DEFAULT_SIZE = 101; //默认散列表大小
  4. private static float LOADFACTOR = 0.75f; //加载因子

构造器

1
2
3
4
5
6
7
8
9
10
11
public SeparateChainingHashTable(){
	this(DEFAULT_SIZE);
}
@SuppressWarnings("unchecked")
public SeparateChainingHashTable(int size){
	theLists = new LinkedList[nextPrime(size)];
	for(int i=0; i < theLists.length; i++)
		theLists[i] = new LinkedList<T>();
	currentSize = 0;
}

散列函数

  hash()：散列函数，计算元素x的散列表，从而得到元素所在的链表的位置。计算散列值是可能会出现溢出的情况，这里做了一个小处理。
  这里的散列函数只是简单的实现，可以通过实现一些更有效的散列函数使得元素在散列表中的分布更均匀。

1
2
3
4
5
6
7
8
private int hash(T x){
	int hashVal = x.hashCode();
	
	hashVal %= theLists.length;
	if(hashVal < 0)
		hashVal += theLists.length;
	return hashVal;
}

  rehash()：重散列函数。当散列表中的元素比例超过加载因子后，为了保证散列表的存取效率，需要对散列表进行扩容操作，然后进行元素的重散列。这样子可以避免具有相同散列码的元素过多，导致相应链表太长，降低了元素的查询效率。

重散列函数主要就是进行两项工作：

  1. 进行散列表大小的扩展；
  2. 重新散列原散列表中的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void rehash(){
	List<T>[] oldList = theLists;
	currentSize = 0;
	
	/* 扩展表的大小 */
	theLists = new LinkedList[nextPrime(2 * oldList.length)];
	for(int i=0; i < theLists.length; i++)
		theLists[i] = new LinkedList<T>();
	
	/* 重新散列元素 */
	for(int i=0; i < oldList.length; i++){
		for(T x : oldList[i])
			insert(x);
	}
}

函数

  clear()：重置哈希表为空表。

1
2
3
4
5
public void clear(){
	for(int i=0; i < theLists.length; i++)
		theLists[i].clear();
	currentSize = 0;
}

  nextPrime()：获取比n大的最小素数。
  isPrime()：判断n是否为素数。
  这里使用了一个技巧，据研究表明散列表大小为素数的话，元素散列后的分布较均匀。（具体可以参考stackoverflow上的一些解释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int nextPrime(int n){
	while(!isPrime(n))
		n++;
	return n;
}
private static boolean isPrime(int n){
	if(n < 2)
		return false;
	
	else{
		for(int i=2; i < Math.sqrt(i); i++)
			if(n%i == 0)
				return false;
	}
	
	return true;
}

  contains()：查询表中是否包含元素x。通过散列码获取到对应的链表，通过链表的contains方法可以实现查找元素功能。

1
2
3
4
public boolean contains(T x){
	List<T> whichList = theLists[hash(x)];
	return whichList.contains(x);
}

  insert()：插入元素x。插入元素的操作大部分时候的花销是很小的(O(1)),因为只要计算出散列码，并在对应的链表里追加元素即可。只有很少的情况下，表的元素比例达到了加载因子的界限，需要对表进行重散列操作，这时候不可避免的花销就大了（O(N)）。

1
2
3
4
5
6
7
8
9
10
11
12
public void insert(T x){
	/* 计算元素的散列码 */
	List<T> whichList = theLists[hash(x)];
	/* 如果链表中没有该元素，则进行插入操作 */
	if(!whichList.contains(x)){
		whichList.add(x);
		
		/* 设装填因子为0.75，当达到装填因子，则进行重散列操作*/
		if(++currentSize == (int)(theLists.length * LOADFACTOR))
			rehash();
	}
}

  remove()：删除元素x。删除元素x是很简单，只需要计算散列码后，从对应的链表中查找是否存在元素x，存在则删除。

1
2
3
4
5
6
7
public void remove(T x){
	List<T> whichList = theLists[hash(x)];
	if(!whichList.contains(x)){
		whichList.remove(x);
		currentSize--;
	}
}

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
import java.util.LinkedList;
import java.util.List;
/**
 * 使用了分离链接来解决冲突方法的散列表实现
 * 存储元素必须实现了equals(),hashCode()方法。
 * @author Bingo
 *
 * @param <T>
 */
public class SeparateChainingHashTable <T>{
    public SeparateChainingHashTable(){
        this(DEFAULT_SIZE);
    }
    @SuppressWarnings("unchecked")
    public SeparateChainingHashTable(int size){
        /* 初始化数组为存储list的数组,这里实际类似二维数组 */
        theLists = new LinkedList[nextPrime(size)];
        for(int i=0; i < theLists.length; i++)
            theLists[i] = new LinkedList<T>();
        currentSize = 0;
    }
    /**
     * 重置哈希表
     */
    public void clear(){
        for(int i=0; i < theLists.length; i++)
            theLists[i].clear();
        currentSize = 0;
    }
    /**
     * 查询散列表中是否包含元素x
     * @param x 
     * @return 包含元素x返回true，否则返回false
     */
    public boolean contains(T x){
        List<T> whichList = theLists[hash(x)];
        return whichList.contains(x);
    }
    /**
     * 在散列表中插入元素x
     * @param x
     */
    public void insert(T x){
        /* 计算元素的散列码 */
        List<T> whichList = theLists[hash(x)];
        /* 如果链表中没有该元素，则进行插入操作 */
        if(!whichList.contains(x)){
            whichList.add(x);
            /* 设装填因子为0.75，当达到装填因子，则进行重散列操作*/
            if(++currentSize == (int)(theLists.length * LOADFACTOR))
                rehash();
        }
    }
    /**
     * 移除元素x
     * @param x
     */
    public void remove(T x){
        List<T> whichList = theLists[hash(x)];
        if(!whichList.contains(x)){
            whichList.remove(x);
            currentSize--;
        }
    }
    private List<T>[] theLists;
    private int currentSize;
    private static int DEFAULT_SIZE = 101;
    private static float LOADFACTOR = 0.75f;
    /**
     * 散列函数,计算x的散列码
     * @param x
     * @return
     */
    private int hash(T x){
        int hashVal = x.hashCode();
        hashVal %= theLists.length;
        if(hashVal < 0)
            hashVal += theLists.length;
        return hashVal;
    }
    /**
     * 重散列表,将表大小加倍,并且重新散列旧表中的元素
     */
    @SuppressWarnings("unchecked")
    private void rehash(){
        List<T>[] oldList = theLists;
        currentSize = 0;
        /* 扩展表的大小 */
        theLists = new LinkedList[nextPrime(2 * oldList.length)];
        for(int i=0; i < theLists.length; i++)
            theLists[i] = new LinkedList<T>();
        /* 重新散列元素 */
        for(int i=0; i < oldList.length; i++){
            for(T x : oldList[i])
                insert(x);
        }
    }
    /**
     * 计算最靠近n的素数
     * @param n
     * @return
     */
    private static int nextPrime(int n){
        while(!isPrime(n))
            n++;
        return n;
    }
    /**
     * 判断一个数是不是素数(简单版)
     * @param n
     * @return
     */
    private static boolean isPrime(int n){
        if(n < 2)
            return false;
        else{
            for(int i=2; i < Math.sqrt(i); i++)
                if(n%i == 0)
                    return false;
        }
        return true;
    }
}

参考资料

  1. 《数据结构与算法分析-java语言描述 第2版》Mark Allen Weiss. 机械工业出版社.