Re: [collections] How about a HashBidiMap?

2017-07-06 Thread Efremov, Rodion 
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 <javenon...@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.efre...@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 <javenon...@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.efre...@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=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
> >
> >
> >
>

Re: [collections] How about a HashBidiMap?

2017-07-06 Thread Javen O'Neal 
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.efre...@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 <javenon...@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.efre...@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=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
> >
> >
> >
>

Re: [collections] How about a HashBidiMap?

2017-07-06 Thread Efremov, Rodion 
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 <javenon...@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.efre...@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=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
>
>
>

Re: [collections] How about a HashBidiMap?

2017-07-06 Thread Javen O'Neal 
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"  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=400] github.com/coderodde/BidirectionalHashMap/blob/
> master/src/net/coderodde/util/BidirectionalHashMap.java>
>
> coderodde/BidirectionalHashMap BidirectionalHashMap/blob/master/src/net/coderodde/util/
> BidirectionalHashMap.java>
> github.com
> BidirectionalHashMap - My implementation of a bidirectional bijective hash
> map in Java
>
>
>