U++ forum: Welcome to the forum

Status & Roadmap

Authors & License

Funding Ultimate++

Search on this site

Search in forums

Home » Community » Coffee corner » Map implementation

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Return to the default flat view

Create a new topic

Submit Reply

Re: Map implementation [message #51548 is a reply to message #51529]

Sat, 13 April 2019 21:25

Novo is currently offline

Novo
Messages: 1358
Registered: December 2006

Ultimate Contributor

mirek wrote on Wed, 10 April 2019 11:37

About the only thing that is in question is how to deal with collisions. Some advanced hashmaps might e.g. use binary trees to resolve collisions. I believe that it is not an overal gain (and the fact that it is not widely used in industry makes it likely) and that we should rather invest time to investigate proper hashing techniques.

Anyway, the real benchmark would be to create real world scenario and test there. IMO U++ Index/VectorMap wins that easily.

AFAIK, STL can't use open addressing or other such techniques because it is specified to maintain stable key/value addresses. U++ Index doesn't support that. This is why it is possible to make it faster.

About collisions. There are many ways to deal with them. A classic approach is to store chain either explicitly (a list) or implicitly (you know how to calculate address of the next colliding slot). I saw a paper from Microsoft recommending an overflow area ...

Basically, what I want to say is that there is a million of different ways to design a hash table.
IMHO, the best way is to split it into multiple policies, so you can easily replace one part of it without rewriting the whole data structure. Smile

Smile

I personally couldn't figure out how to do that. Smile

Smile

Regards,
Novo

Report message to a moderator

Send a private message to this user

[Message index]

		Map implementation By: cbpporter on Thu, 21 March 2019 16:32
		Re: Map implementation By: mirek on Fri, 22 March 2019 07:18
		Re: Map implementation By: Novo on Wed, 27 March 2019 03:33
		Re: Map implementation By: cbpporter on Tue, 02 April 2019 14:13
		Re: Map implementation By: Novo on Tue, 02 April 2019 17:48
		Re: Map implementation By: Novo on Tue, 02 April 2019 18:39
		Re: Map implementation By: cbpporter on Mon, 08 April 2019 13:57
		Re: Map implementation By: mirek on Mon, 08 April 2019 22:37
		Re: Map implementation By: cbpporter on Tue, 09 April 2019 14:57
		Re: Map implementation By: mirek on Tue, 09 April 2019 17:16
		Re: Map implementation By: mirek on Wed, 10 April 2019 11:07
		Re: Map implementation By: cbpporter on Wed, 10 April 2019 11:39
		Re: Map implementation By: Novo on Wed, 10 April 2019 17:09
		Re: Map implementation By: mirek on Wed, 10 April 2019 17:37
		Re: Map implementation By: Novo on Sat, 13 April 2019 20:58
		Re: Map implementation By: Novo on Sat, 13 April 2019 21:07
		Re: Map implementation By: mirek on Sun, 14 April 2019 08:03
		Re: Map implementation By: Novo on Sun, 14 April 2019 18:55
		Re: Map implementation By: mirek on Sun, 14 April 2019 19:52
		Re: Map implementation By: mirek on Tue, 16 April 2019 12:38
		Re: Map implementation By: Novo on Tue, 16 April 2019 16:38
		Re: Map implementation By: mirek on Tue, 16 April 2019 19:33
		Re: Map implementation By: Novo on Tue, 16 April 2019 22:36
		Re: Map implementation By: Novo on Wed, 17 April 2019 05:40
		Re: Map implementation By: mirek on Wed, 17 April 2019 08:54
		Re: Map implementation By: Novo on Wed, 17 April 2019 16:13
		Re: Map implementation By: mirek on Wed, 17 April 2019 18:39
		Re: Map implementation By: mirek on Fri, 07 June 2019 13:58
		Re: Map implementation By: Novo on Tue, 25 June 2019 15:20
		Re: Map implementation By: mirek on Wed, 26 June 2019 12:07
		Re: Map implementation By: Novo on Mon, 01 July 2019 06:26
		Re: Map implementation By: mirek on Mon, 01 July 2019 17:53
		Re: Map implementation By: Novo on Sat, 13 April 2019 21:25
		Re: Map implementation By: Novo on Wed, 10 April 2019 16:13
		Re: Map implementation By: mirek on Wed, 10 April 2019 17:50
		Re: Map implementation By: Novo on Wed, 10 April 2019 16:48

Previous Topic:	[Skylark][witz] How would you do this
Next Topic:	[SOLVED]Sharing Ptr of object to dll

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

PDF

]

Current Time: Thu Apr 18 07:10:22 CEST 2024

Total time taken to generate the page: 0.01360 seconds