commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Efremov, Rodion" <rodion.efre...@helsinki.fi>
Subject Re: [collections] How about a HashBidiMap?
Date Thu, 06 Jul 2017 10:22:37 GMT
Having taking a closer look the way DualHashBidiMap and Java's HashMap are implemented, my
implementation has only two advantages:


(1) It maintains an additional list of entries. This allows faster iteration since it does
not have to visit empty collision chain buckets. Also, it allows faster relinking of the mapping
objects when making the hash tables larger. (I believe this may be alleviated by using LinkedHashMaps
in DualHashBidiMap instead of HashMaps.)


(2) Collision "chains" are actually collision (AVL) trees; this allows worst case logarithmic
modification/access in case the hash function is poor.


What would your opinion on the above arrangements?


Best regards,

Rodion



________________________________
From: Javen O'Neal <javenoneal@gmail.com>
Sent: Thursday, July 6, 2017 1:11:23 PM
To: Commons Developers List
Subject: Re: [collections] How about a HashBidiMap?

It wasn't a rhetorical question. I wanted to open discussion on your
contribution, and wanted to start with what folks on this mailing list are
most familiar with.

I'm not a Commons Collection maintainer, but I'm curious if you could
describe your implementation in a few sentences and how it differs from the
current DualHashBidiMap implementation. Is it faster than other
implementations? Does it have a lower memory footprint by sharing key and
value objects between two underlying HashMaps? Does it implement its own
HashMap interface implementing its own Map data structure?

Can you name one or two scenarios where your implementation would be
preferred over the existing implementations?

On Jul 6, 2017 11:56, "Efremov, Rodion" <rodion.efremov@helsinki.fi> wrote:

> From
> http://svn.apache.org/viewvc/commons/proper/collections/
> trunk/src/main/java/org/apache/commons/collections4/
> bidimap/DualHashBidiMap.java?view=markup
>
> "Commons Collections would welcome the addition of a direct hash-based
> implementation of the BidiMap interface"
>
> Guess I was wrong.
>
> ________________________________
> From: Javen O'Neal <javenoneal@gmail.com>
> Sent: Thursday, July 6, 2017 12:51:25 PM
> To: Commons Developers List
> Subject: Re: [collections] How about a HashBidiMap?
>
> How is this different from the existing DualHashBidiMap?
>
> https://commons.apache.org/proper/commons-collections/
> javadocs/api-release/org/apache/commons/collections4/
> bidimap/DualHashBidiMap.html
>
> On Jul 6, 2017 09:06, "Efremov, Rodion" <rodion.efremov@helsinki.fi>
> wrote:
>
> > Hello,
> >
> >
> > I am working on a hash table based BidiMap at
> > https://github.com/coderodde/BidirectionalHashMap/blob/
> > master/src/net/coderodde/util/BidirectionalHashMap.java
> >
> > and would like to contribute it to Commons Collections. Could someone
> > working on the project discuss my contribution attempt?
> >
> >
> > Best regards,
> >
> > Rodion
> >
> > [https://avatars2.githubusercontent.com/u/1770505?v=3&s=400]<https://
> > github.com/coderodde/BidirectionalHashMap/blob/
> > master/src/net/coderodde/util/BidirectionalHashMap.java>
> >
> > coderodde/BidirectionalHashMap<https://github.com/coderodde/
> > BidirectionalHashMap/blob/master/src/net/coderodde/util/
> > BidirectionalHashMap.java>
> > github.com
> > BidirectionalHashMap - My implementation of a bidirectional bijective
> hash
> > map in Java
> >
> >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message