More importantly, how do you get a nice hash key?
You can iterator over contents on a simple array, store the keys there like:
string hashKeys[];
That's what you usually use to iterate over when doing hashmaps anyway (if
you want to iterate over contents what do you need the hash for?)
Here's a pseudocode attempt at a hashset (I keep forgetting the subtleties
of @ and the autogrowing array syntax is missing from the annoying manual):
class HashElement {
fun int hashCode();
}
class HashSet {
HashElement elements[][];
fun int contains(HashElement @ element) {
elements[element.hashCode()] @=> HashElement @ hashedList[];
for (0 => int i; i < hashedList.cap(); i++) {
if (hashedList[i] == element) {
return 1;
}
}
return 0;
}
fun void insert(HashElement @ element) {
elements[element.hashCode()] @=> HashElement @ hashedList[];
if (hashedList == null) {
HashElement[1] @=> hashedList;
hashedList @=> elements[element.hashCode()];
}
element +=> hashedList[]; // keep forgetting the syntax for
autogrowing the array
}
}
The elements you want to put in the hash set need to extend HashElement.
/Stefan
2009/9/30 Robert Poor
Hans: Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents.
- Rob
On 30 Sep 2009, at 02:03, Hans Aberg wrote:
On 30 Sep 2009, at 02:13, Robert Poor wrote:
I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?
For lookup tables, if you do not need to compare the keys, a hash map is fastest - time complexity O(1), otherwise a balanced tree (like C++ std::map) - complexity O(log n). There might be some C++ hash map classes at http://www.boost.org/. But if n is small and use not too intense, just about any container will do.
Hans
_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users
-- Release me, insect, or I will destroy the Cosmos!