KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > runtime > HashMapOfString


1 /*******************************************************************************
2  * Copyright (c) 2005 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.core.internal.runtime;
12
13 import org.eclipse.core.internal.preferences.StringPool;
14
15 /**
16  * Hashtable of {String --> String}.
17  *
18  * This map handles collisions using linear probing. When elements are
19  * removed, the entire table is rehashed. Thus this map has good space
20  * characteristics, good insertion and iteration performance, but slower
21  * removal performance than a HashMap.
22  * <p>
23  * This map is not thread safe.
24  */
25 public final class HashMapOfString {
26     /**
27      * number of elements in the table
28      */
29     private int elementSize;
30     /**
31      * The table keys
32      */
33     private String JavaDoc[] keyTable;
34
35     private int threshold;
36
37     private String JavaDoc[] valueTable;
38     private static final float LOAD_FACTOR = 0.45f;
39
40     public HashMapOfString() {
41         this(16);
42     }
43
44     public HashMapOfString(int size) {
45         this.elementSize = 0;
46         //table size must always be a power of two
47 int tableLen = 1;
48         while (tableLen < size)
49             tableLen *= 2;
50         this.keyTable = new String JavaDoc[tableLen];
51         this.valueTable = new String JavaDoc[tableLen];
52         this.threshold = (int) (tableLen * LOAD_FACTOR);
53     }
54
55     public String JavaDoc get(String JavaDoc key) {
56         int lengthMask = keyTable.length - 1;
57         int index = key.hashCode() & lengthMask;
58         String JavaDoc currentKey;
59         while ((currentKey = keyTable[index]) != null) {
60             if (currentKey.equals(key))
61                 return valueTable[index];
62             index = (index+1) & lengthMask;
63         }
64         return null;
65     }
66
67     public boolean isEmpty() {
68         return elementSize == 0;
69     }
70
71     /**
72      * Returns an array of all keys in this map.
73      */
74     public String JavaDoc[] keys() {
75         String JavaDoc[] result = new String JavaDoc[elementSize];
76         int next = 0;
77         for (int i = 0; i < keyTable.length; i++)
78             if (keyTable[i] != null)
79                 result[next++] = keyTable[i];
80         return result;
81     }
82
83     public String JavaDoc put(String JavaDoc key, String JavaDoc value) {
84         int lengthMask = keyTable.length - 1;
85         int index = key.hashCode() & lengthMask;
86         String JavaDoc currentKey;
87         while ((currentKey = keyTable[index]) != null) {
88             if (currentKey.equals(key))
89                 return valueTable[index] = value;
90             index = (index+1) & lengthMask;
91         }
92         keyTable[index] = key;
93         valueTable[index] = value;
94
95         // assumes the threshold is never equal to the size of the table
96 if (++elementSize > threshold)
97             rehash(keyTable.length * 2);
98         return value;
99     }
100
101     private void rehash(int newLen) {
102         HashMapOfString newHashtable = new HashMapOfString(newLen);
103         String JavaDoc currentKey;
104         int oldLen = keyTable.length;
105         for (int i = oldLen; --i >= 0;)
106             if ((currentKey = keyTable[i]) != null)
107                 newHashtable.put(currentKey, valueTable[i]);
108         this.keyTable = newHashtable.keyTable;
109         this.valueTable = newHashtable.valueTable;
110         this.threshold = newHashtable.threshold;
111     }
112
113     public String JavaDoc removeKey(String JavaDoc key) {
114         int lengthMask = keyTable.length - 1;
115         int index = key.hashCode() & lengthMask;
116         String JavaDoc currentKey;
117         while ((currentKey = keyTable[index]) != null) {
118             if (currentKey.equals(key)) {
119                 String JavaDoc value = valueTable[index];
120                 elementSize--;
121                 keyTable[index] = null;
122                 valueTable[index] = null;
123                 rehash((int) (elementSize / LOAD_FACTOR));
124                 return value;
125             }
126             index = (index+1) & lengthMask;
127         }
128         return null;
129     }
130
131     /* (non-Javadoc
132      * Method declared on IStringPoolParticipant
133      */
134     public void shareStrings(StringPool set) {
135         //copy elements for thread safety
136 String JavaDoc[] array = keyTable;
137         if (array == null)
138             return;
139         for (int i = 0; i < array.length; i++) {
140             String JavaDoc o = array[i];
141             if (o != null)
142                 array[i] = set.add(o);
143         }
144         array = valueTable;
145         if (array == null)
146             return;
147         for (int i = 0; i < array.length; i++) {
148             String JavaDoc o = array[i];
149             if (o != null)
150                 array[i] = set.add(o);
151         }
152     }
153
154     public int size() {
155         return elementSize;
156     }
157
158     public String JavaDoc toString() {
159         String JavaDoc s = ""; //$NON-NLS-1$
160 String JavaDoc value;
161         for (int i = 0, length = valueTable.length; i < length; i++)
162             if ((value = valueTable[i]) != null)
163                 s += keyTable[i] + " -> " + value.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
164 return s;
165     }
166 }
Popular Tags