Nth element of a hash?

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

(hash-nth (random n) myHash)

Siggy

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.

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

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.

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

A seperate vector would be gross.

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