Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #8591

How best to implement a hash table in Mathematica

From Joseph Gwinn <joegwinn@comcast.net>
Newsgroups comp.soft-sys.math.mathematica
Subject How best to implement a hash table in Mathematica
Date 2012-02-18 11:28 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <jho21j$5sb$1@smc.vnet.net> (permalink)

Show all headers | View raw


I have an application that resembles dictionary lookup, with significant 
rates of collision.  

The current approach is to initialize the hash table, a 10^4 element 
list of empty sublists, and then build the table by inserting document 
object id numbers into the correct sublists as indexed by some important 
property of the object.  The choice of property varies with application.  
The property may be quantized geographic location, or some attribute of 
the object itself.

When done building the hash table, query consists of reading the sublist 
using an index derived in the same way as for the original building of 
the list.  Each sublist may have many entries, and the entries need not 
be numbers.

Anyway, I have a workable approach using 

HashList[[index]]=
Union[Flatten[Join[HashList[[index]],{new object ID}]]]]

as the core update function, but I'm wondering how well this will scale 
to say 10^6 sublists (which may be needed to keep the collisions under 
control with large datasets), and of course if there is a better way in 
Mathematica.

I did look at SparseArrays, but they don't support elements that are 
sublists.

Although this hash table is one dimensional, I have uses for 2D and 
maybe 3D tables, which are very common when one is hashing physical 
location.

Thanks in advance,

Joe Gwinn

Back to comp.soft-sys.math.mathematica | Previous | Next — Next in thread | Find similar | Unroll thread


Thread

How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-18 11:28 +0000
  Re: How best to implement a hash table in Mathematica Szabolcs Horvát <szhorvat@gmail.com> - 2012-02-19 11:29 +0000
    Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:50 +0000
  Re: How best to implement a hash table in Mathematica David Bailey <dave@removedbailey.co.uk> - 2012-02-19 11:36 +0000
    Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:48 +0000
      Re: How best to implement a hash table in Mathematica A Retey <awnl@gmx-topmail.de> - 2012-02-21 11:20 +0000
        Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:36 +0000
      Re: How best to implement a hash table in Mathematica Szabolcs Horvát <szhorvat@gmail.com> - 2012-02-21 11:21 +0000
        Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:35 +0000
  Re: How best to implement a hash table in Mathematica Richard Fateman <fateman@cs.berkeley.edu> - 2012-02-19 11:36 +0000
    Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:49 +0000
      Re: How best to implement a hash table in Mathematica Richard Fateman <fateman@cs.berkeley.edu> - 2012-02-21 11:11 +0000
        Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:36 +0000
  Re: How best to implement a hash table in Mathematica Leonid Shifrin <lshifr@gmail.com> - 2012-02-22 10:34 +0000
    Re: How best to implement a hash table in Mathematica "Nasser M. Abbasi" <nma@12000.org> - 2012-02-23 10:51 +0000
  Re: How best to implement a hash table in Mathematica Leonid Shifrin <lshifr@gmail.com> - 2012-02-24 06:00 +0000

csiph-web