散列表

博客分类：

• 数据结构 数据结构

【散列表】 它是用一个散列函数把关键字 映射到散列表中的特定位置。 在理想情况下，如果元素e 的关键字为k，散列函 数为f，那么e 在散列表中的位置为f (k)。要搜索关键字为k 的元素，首先要计算出f (k)，然后看 表中f (k)处是否有元素。如果有，便找到了该元素。如果没有，说明该字典中不包含该元素。 在前一种情况中，如果要删除该元素，只需把表中f (k)位置置为空即可。在后一种情况中，可 以通过把元素放在f (k)位置以实现插入。 此例是一个理想情况下的散列表，不考虑关键字重复的情况

Java代码

1. public class HashList {
3. private String[] table;
5. private int size;
7. private int threshold;
9. private static final int INITIAL_CAPACITY = 10;
11. private static final int SIZE_INCREASE = 10;
13. private static final float DEFAULT_LOAD_FACTOR = 0.75f;
17. public HashList(){
18. threshold = (int)(INITIAL_CAPACITY/*DEFAULT_LOAD_FACTOR);
19. table = new String[INITIAL_CAPACITY];
20. }
24. public HashList(String[] table){
25. this.table = table;
26. }
31. ///
32. /* Get the actual size of the list
33. /* @return
34. /*/
35. public int size(){
36. return size;
37. }
39. ///
40. /* for test
41. /* @return
42. /*/
43. public String[] getElements(){
44. return table;
45. }
47. public boolean contains(String element) {
48. if (element == null) {
49. return false;
50. }
51. if (element.equals(table[getIndex(element)])) {
52. return true;
53. }
54. return false;
55. }
57. public void add(String element){
58. int index = getIndex(element);
59. if(size>threshold){
60. resize();
61. }
62. table[index] = element;
63. size++;
64. }
68. //private methods
69. ///
70. /* resize the array
71. /*/
72. private void resize(){
73. String[] newArray = new String[table.length+SIZE_INCREASE];
74. for(int i=0;i<table.length;i++){
75. newArray[i] = table[i];
76. }
77. table = newArray;
78. threshold = (int)(table.length/*DEFAULT_LOAD_FACTOR);
79. }
81. ///
82. /* get the index of the element
83. /* @param element
84. /* @return
85. /*/
86. public int getIndex(String element) {
87. return (element.hashCode() & 0x7FFFFFFF) % table.length;
88. }
89. }

来源： [http://tangyanbo.iteye.com/blog/1476372](http://tangyanbo.iteye.com/blog/1476372)