Nth element of a hash?

[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

Code: Select all

(hash-nth (random n) myHash)

Siggy

[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.

[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

[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.

[SigmaX]

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

[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))