Nth element of a hash?

Discussion of Common Lisp
Post Reply
SigmaX
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Nth element of a hash?

Post by SigmaX » Wed Jul 28, 2010 1:11 pm

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
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Nth element of a hash?

Post by ramarren » Wed Jul 28, 2010 2:20 pm

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
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Re: Nth element of a hash?

Post by SigmaX » Wed Jul 28, 2010 3:49 pm

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 :-P.

Didn't know about skip-lists. Learned something new :-).

Cheers,
Siggy

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Nth element of a hash?

Post by gugamilare » Thu Jul 29, 2010 6:20 am

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
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Re: Nth element of a hash?

Post by SigmaX » Thu Jul 29, 2010 9:24 am

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

Warren Wilkinson
Posts: 117
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta
Contact:

Re: Nth element of a hash?

Post by Warren Wilkinson » Tue Aug 10, 2010 11:44 pm

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))
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.

Post Reply