Page 1 of 1
Nth element of a hash?
Posted: Wed Jul 28, 2010 1:11 pm
by SigmaX
So, I've got a weird one. What if I want to access the nth element of a hash table, much as one would with (nth myList)?
I know, I know, "why would you want to that that? A hash doesn't even have a guaranteed order!"
What I'm really trying to do is select a random element from a hash, and I want a more efficient way of doing it than iterating through each row 'till I reach my randomly-chosen index. So I want something like
Siggy
Re: Nth element of a hash?
Posted: Wed Jul 28, 2010 2:20 pm
by ramarren
Well, as you note hash-table does not have an order, which means that such operation is meaningless. It would be in principle possible to access the underlying implementation, but that is not really a good idea, since buckets are obviously not filled sequentially, so you would still need to do scanning.
If you really need efficiency here, then maintain a vector with the values you want to retrieve. Another alternative would be to use an ordered associative data structure like an appropriate tree, or possibly a skip list. This would put a logarithmic complexity on most operations, but it might cheaper than maintaining a value vector if it is in constant flux.
Re: Nth element of a hash?
Posted: Wed Jul 28, 2010 3:49 pm
by SigmaX
Okay. All I really needed to know is whether CL's hash table implementation had some feature I don't know about.
I'll probably maintain a separate vector of the keys specifically for this purpose. The random selection only occurs in one particular function, and I'm pretty sure the hash will be more efficient for the rest of the program. In any event, it will be waaay better than the unordered associative list I was using before
.
Didn't know about skip-lists. Learned something new
.
Cheers,
Siggy
Re: Nth element of a hash?
Posted: Thu Jul 29, 2010 6:20 am
by gugamilare
Why do you want to access the nth element of a hash-table? If what you want is to access all elements of the hash-table sequentially you should use
maphash or
loop.
Re: Nth element of a hash?
Posted: Thu Jul 29, 2010 9:24 am
by SigmaX
gugamilare wrote:Why do you want to access the nth element of a hash-table? If what you want is to access all elements of the hash-table sequentially you should use
maphash or
loop.
You must have skipped the original post. I explained why: to access a
random element.
Siggy
Re: Nth element of a hash?
Posted: Tue Aug 10, 2010 11:44 pm
by Warren Wilkinson
A seperate vector would be gross.
Code: Select all
(defun nthhash (n h) (maphash #'(lambda (k v) (when (zerop n) (return-from nthhash (values v k))) (decf n)) h))
(setf *test* (make-hash-table))
(setf (gethash :a *test*) :aa)
(setf (gethash :b *test*) :bb)
(setf (gethash :c *test*) :cc)
(nthhash 0 *test*) ;; gives :a :aa
(nthhash 1 *test*) ;; gives :b :bb
(nthhash 2 *test*) ;; gives :c :cc
(nthhash 3 *test*) ;; gives nil
(defun randhash (h) (nthhash (random (hash-table-count h)) h))