Getting the Hashtable values by partial key
Hello JDC
I have a question about Hashtable. Lets assume that you put the following key in the Hashtable:
hashtable.put(my name is Shay ,my family name is Gaghe )
In general circumstances whenever you need the value my family name is Gaghe you code:
String value = (String)Hastable.get(my name is Shay );
But what if you must get the value my family name is Gaghe only with Shayinstead my name is Shay as a key :
String value = (String)Hastable.get(Shay );
Is that possible?
Thanks in advance
Shay Gaghe
[579 byte] By [
samifox] at [2007-9-26 7:31:30]
If you use a partial key, it's possible that there is more than one entry in the collection that matches it. So clearly you would need an object that returned an array or a list or something. Hashtable is not the right collection to use for this type of search, I would look at using a TreeMap if I were you.
OK I'm going out on a limb here. You could create a class that wraps a String and override the equals() method to use the indexOf() method and add this to your HashTable. If indexOf returns 0 or greater then return equals. Important: In order to follow the rules of overriding the equals method you must several things. Instead of trying to related them I will just give an example.
class StringWrapper {
private String string;
StringWrapper(String string) {
this.string = string;
}
public String toString() {
return string;
}
public boolean equals(Object object) {
if (object.getClass() == this.getClass()) {
return equals((StringWrapper) object);
} else {
return false;
}
}
public boolean equals(StringWrapper stringWrapper) {
return (string.indexOf(stringWrapper.toString()) >= 0) |
(stringWrapper.toString().indexOf(string) >= 0);
}
}
Note: > is the greater than symbol
P.S. I think HashMap is preferred over HashTable.
> If you use a partial key, it's possible that there is
> more than one entry in the collection that matches it.
> So clearly you would need an object that returned an
> array or a list or something. Hashtable is not the
> right collection to use for this type of search, I
> would look at using a TreeMap if I were you.
Are you saying that you can add more than one value to a key in a tree map? It doesn't seem like that is what the API says. I thought the TreeMap was essentially the same as a HashMap except that it "provides guaranteed log(n) time cost for the containsKey, get, put and remove operations."
As to what DrClap is saying. My class I created will limit your ability to add keys. You wouldn't be able to add "a" and "ab" because these would be considered equal and one would replace the other.
The other way to do this that I didn't mention is to just have a plain old looping search of the keys. You can get a collection of all the keys and then loop through them checking each one to see if it contains your string. THe problem with this is that it could get really slow as the map gets large. n / 2 time.
TreeMap was probably suggested because it is ordered. If you retrieve an array of all keys with a certain String from Hashtable, these keys will not be in any particular order, but, if done from TreeMap, they will be ordered according to the natural ordering of the String class, thus making your logic easier... ..... why would you need to retrieve all elements with a comparable key? If these elements are all members of some group, say all with keys like "customer1", "customer2", it would be better to strore them as a group so you are running less expensive operations. IE:
hash.put("customer", cusomters);
ArrayList customers = (ArrayList)hash.get("customers");
> TreeMap was probably suggested because it is ordered.
> If you retrieve an array of all keys with a certain
> String from Hashtable, these keys will not be in any
> particular order, but, if done from TreeMap, they
> will be ordered according to the natural ordering of
> the String class, thus making your logic easier...
> ..... why would you need to retrieve all elements
> with a comparable key? If these elements are all
> members of some group, say all with keys like
> "customer1", "customer2", it would be better to
> strore them as a group so you are running less
> expensive operations. IE:
>
> hash.put("customer", cusomters);
> ArrayList customers =
> = (ArrayList)hash.get("customers");
I hear what you all are saying but I just don't think it applies to the original question. Look at it closely. It doesn't say anything about grouping at all. The orginal question says if I put in a key like "ab" can I find it by looking for "a". Are you suggestting that if I wanted to do this with a key "abc" that I should actually add a key "a", a key "b", a key "c", a key "ab", a key "bc", and a key "abc"? Unless this is what you suggest your solution requires that the developer knows what substring will be searched on before looking for it which makes the whole point of the question moot. If I am misintrepreting your post please correct me.
No. What I was suggesting is that if you have a Hashtable that is holding application inforamtion, say customer data and company data, rather then hold them in format
hash.put("customer1", customer)
hash.put("customer2", customer2)
hash.put("company1", company)
it would be better to do,
hash.put("customers", Vector customers);
hash.put("company", Vector companies);
To be honest, I never even read the original message- I was just responding to who ever asked about the advantage of TreeMap (I'm not much of a details man... sorry for ignoring the original post).
Any ways, it seems to me, that you would only perform String comparisons on keys if a) the calling resource does not know the full String or b) the pattern in the key actually signifies that the element is part of some group.
I question the merit of either approach. It seems to me that you should just use the key name. If you are searching for keys that need to support multiple search criteria, like a FamilyName class that can be compared via first or last name or both, then you should, in my view, write a class that implements Comparable as such and store each element in a List (which seems to be what, or close to what, you were suggesting in a previous post).I'm not convinced that a String comparison on keys is the best approach.
>I hear what you all are saying but I just don't think it applies to the original question. Look at it closely. It doesn't say anything about grouping at all. The orginal question says if I put in a key like "ab" can I find it by looking for "a".
I don't mean to interpret what rvflannery said, but in response to this: No, the original question doesn't say anything about grouping. But it SHOULD. If you put in a key like "ab" then maybe you can twist a Hashtable to find it by looking for "a". But if you put in another key like "abc", what should you get if you look for "a"? Well I don't know, the design doesn't address that question. There's really no point writing code when you don't have important design questions answered, and that's an important design question. My guess at the answer was that you would want all keys that start with "a" returned, and for that I think you would be better to start with a TreeMap, yes because it is ordered, and also because it appears to provide a method for getting a subset whose keys are in a particular range. But that was just a quick suggestion based (as I said) on a rough design. Personally I would use a database for that (Select * from NameTable where Name Like 'a*').
Thank you all for your repliesI may take advantage of your interesting ideas but in the other hand i truly think that the Java team has to provide an object that allows performing a search by a substring: String value = (String)hashtable.get(*Shay)repliesShay Gaghe
if you like, you could provide that functionality by extending Hashtable and writing a method called, getPartialMatch() or some thing.
However, searching for a "partial match" is totally incompatible with the notion of a hash table.
The whole reason that you use a hash table is to get O(1) performance on insertions, deletions, and lookups. This is done by finding the hashcode of objects, and using that number to quickly find the the object in the table. If you want to determine which elements "match" a particular pattern, this hashing scheme won't work.
Hello,
My point of view is that an HashTable object is not the "right" structure to search a set of values indexed by keys which must start with a specific pattern.
DrClap has suggested to use a TreeMap and I think also that the underlying structure is more interesting in this case:
An HashTable can be break apart into 2 components:
(1) An array which will be used to store the references; and
(2) An hash function.
The put() function performs the following operations:
Firstly, it computes from the provided key / object an index:
index = (key.hashCode() & binary) % (sizeof the underlying array).
I do not remenber the value of binary but the & operation is performed only to ensure that the value is positive and thus that the % operator returns an integer greater than zero (or zero).
Secondly, it inserts at the index position of the underlying array the key and its reference / value.
The get() function performs the following operations:
Firstly, it generates the index from the key.
Secondly, it retrieves the elements, there may be one or more than one, at the index position in the underlying array.
Thirdly, it compares the keys of the elements one by one with the specified key until the right key is encountered.
So the complexity of research is function of the density of the hash function. Moreover, as the indexes computed from "a" and "ab" are not the same, one must jump from one location to an other one to retrieve the values which is very inefficient. Moreover none of the "a", "ab" and "abc" keys have the same index (I have not verified but the probabilities are on my side). I let you guess now that to retrieve all the elements indexed by keys starting with "a" it is more interesting to traverse explicitly all the elements of the array. Hence, an HashTable was used to "index" some elements, in other words to improve the search operations, and at the end one does not use the structure.
A TreeMap is a balance-tree. Hence, the complexity of the put and get functions is function of the height of the tree: log(n). Moreover, the put function mechanism keep the tree balanced and sorted. As it is balance, the complexity is always log(n) and as it is sorted, one can easily extract a branch of this tree which list all the elements starting with the "a" character (a good comparison function must although be used.).
I hope it helps,
Gianny
U can try as somebody above ponted out creating a custom Hashtable by extending it. something like this.
package java.test;
import java.util.*;
public class NameStorage extends java.util.Hashtable {
public NameStorage() {
super();
}
public NameStorage(int initialCapacity) {
super(initialCapacity);
}
public NameStorage(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
}
public NameStorage(java.util.Map t) {
super(t);
}
public Object get(Object objKey)
{
//As a first effort see whether there is an element with
//objKey as the exact value;
Object objValue = super.get(objKey);
if(objValue != null)
{
return objValue;
}else
{
Enumeration allNames = this.keys();
String strName=null;
while (allNames.hasMoreElements())
{
strName = (String)allNames.nextElement();
if(strName.toUpperCase().indexOf(((String)objKey).toUpperCase()) >= 0)
{
objValue= super.get(strName);
}
}
}
return objValue;
}
public static void main(String[] args)
{
NameStorage names = new NameStorage();
names.put("One","Name one");
names.put("Two","Name two");
System.out.println("name tow:" + (String)names.get("Two"));
System.out.println("name tow:" + (String)names.get("wo"));
System.out.println("name tow:" + (String)names.get("zo"));
}
}
