Re: Data structure for fast associative array with lookup by both key and index

Gene wrote:
On May 26, 2:17 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
Gene wrote:
On May 26, 5:23 am, "A.J." <naijir...@xxxxxxxxx> wrote:

I'm looking for a data structure for an associative array with the
following properties:

... snip ...

CBFalconer's hashlib is excellent, but I'm guessing from your design
that you need deletions to "collapse" the array index space so there
are no holes. I can't see a way this can be done in O(1). The order
stats tree is a nice O(log n) solution. You pay O(log n) on insert
(with respect to a hash table e.g.) in order to allow deletions to be
O(log n) rather than O(n).

Thanks. However hashlib can do O(1) deletions. The hashwalk
function allows compression to a single list at any time (O(N)).
The result is invalid after further insertion/deletions, but will
survive searches. It also seems to be accurate, in that I have had
no reports of flaws in several years.

Thanks. But I guess I'm not clear on what you're proposing. If you
add A, C, D to initially empty x then x[1]=A, x[2]=C, x[3]=D. Now
delete A. You are saying that moving C and D to positions x[1] and
x[2] will require O(n). Yes? With the order statistics tree, the
deletion remains O(log n). That's what I was getting at.

A hash table is NOT an array. Things don't normally get moved.
Get it and look. It's not that big.


--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages