[collections] How about a HashBidiMap?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[collections] How about a HashBidiMap?

Efremov, Rodion
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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [collections] How about a HashBidiMap?

Javen O'Neal-2
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" <[hidden email]> 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
>
>
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [collections] How about a HashBidiMap?

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 <[hidden email]>
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" <[hidden email]> 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
>
>
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [collections] How about a HashBidiMap?

Javen O'Neal-2
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" <[hidden email]> 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 <[hidden email]>
> 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" <[hidden email]>
> 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
> >
> >
> >
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [collections] How about a HashBidiMap?

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 <[hidden email]>
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" <[hidden email]> 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 <[hidden email]>
> 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" <[hidden email]>
> 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
> >
> >
> >
>
Loading...