473,714 Members | 3,296 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

STL Map uses hashing?

I am reading about hashing techniques. The map data structure
available in C++ STL uses hashing techniques?
Jun 27 '08 #1
15 3002
Vinodh wrote:
I am reading about hashing techniques. The map data structure
available in C++ STL uses hashing techniques?
std::map std::multimap std::set std::multiset are often implemented
using Red-Black Tree

In tr1, there are unordered_xxx types using hash table
which were implemented by some vendors as hash_xxx for extension before tr1

--
Best Regards
Barry
Jun 27 '08 #2
In article <4353ee37-4fa4-4bc0-924f-482523333e21
@u12g2000prd.go oglegroups.com> , pv**********@gm ail.com says...
I am reading about hashing techniques. The map data structure
available in C++ STL uses hashing techniques?
No -- it uses a balanced tree of some sort (e.g. AVL or red-black tree).

TR1 (and C++ 0x) add unordered_[multi]set and unordered_[multi]map,
which are intended to be based on hashing.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #3
In article <MP************ ************@ne ws.sunsite.dk>,
Jerry Coffin <jc*****@taeus. comwrote:
>In article <4353ee37-4fa4-4bc0-924f-482523333e21
@u12g2000prd.g ooglegroups.com >, pv**********@gm ail.com says...
>I am reading about hashing techniques. The map data structure
available in C++ STL uses hashing techniques?

No -- it uses a balanced tree of some sort (e.g. AVL or red-black tree).
For information, this is because of requirements:

A STL map is required to have a worse case find() of O log(N).
Balanced trees give you that. Although hash maps are typically faster
than balanced tree on large amount of random data, they do not
guarantee a worse case scenario of O log(N).

>TR1 (and C++ 0x) add unordered_[multi]set and unordered_[multi]map,
which are intended to be based on hashing.
I.e. TR1 did accept that hash maps are also useful and added them.
Now all we need is for the developpers to be able to make an informed
choice on the correct one to use for a particular application. :-)

Yan


Jun 27 '08 #4
On May 30, 4:28 pm, ytrem...@nyx.ny x.net (Yannick Tremblay) wrote:
In article <MPG.22a85e2e38 d3b341989...@ne ws.sunsite.dk>,
Jerry Coffin <jcof...@taeus. comwrote:
In article <4353ee37-4fa4-4bc0-924f-482523333e21
@u12g2000prd.go oglegroups.com> , pvinodhku...@gm ail.com says...
I am reading about hashing techniques. The map data structure
available in C++ STL uses hashing techniques?
No -- it uses a balanced tree of some sort (e.g. AVL or
red-black tree).
For information, this is because of requirements:
A STL map is required to have a worse case find() of O log(N).
Balanced trees give you that. Although hash maps are
typically faster than balanced tree on large amount of random
data, they do not guarantee a worse case scenario of O log(N).
I don't know about the "typically faster". Their average access
time is faster IF the hash function is good. Typically, I find
that it's not always that good (although the situation is
improving).

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Jun 27 '08 #5
James Kanze wrote:
I don't know about the "typically faster". Their average access
time is faster IF the hash function is good. Typically, I find
that it's not always that good (although the situation is
improving).
Question: Will the new C++ standard require for the libraries to
provide high-quality default hashing functions for internal types (and
perhaps some other standard types such as std::string), or will the user
be forced to always provide one himself?

Creating good-quality hashing functions are not a trivial task at all
(and the subject of continuing extensive research). One cannot expect
the average user to invent a good-quality function without extensive
knowledge and experience on the subject.
Jun 27 '08 #6
On 2008-05-31 11:50:57 -0400, Juha Nieminen <no****@thanks. invalidsaid:
James Kanze wrote:
>I don't know about the "typically faster". Their average access
time is faster IF the hash function is good. Typically, I find
that it's not always that good (although the situation is
improving).

Question: Will the new C++ standard require for the libraries to
provide high-quality default hashing functions for internal types (and
perhaps some other standard types such as std::string), or will the user
be forced to always provide one himself?
"High quality" depends on the distribution of the actual values that
you're using. A "high quality" integer hash function for one
application may be an utter failure in another application.
>
Creating good-quality hashing functions are not a trivial task at all
(and the subject of continuing extensive research). One cannot expect
the average user to invent a good-quality function without extensive
knowledge and experience on the subject.
Indeed. That's why I've never thought that standardizing hashed
containers was a good idea. There's just too much flexibility, making
them hard to specify well, with the result that naive users can get
horrible performance without knowing why.

But, to answer your question, no, there is no requirement for "high
quality" hashing functions. Implementations will be required to provide
hashing functions for the builtin types, pointers, std::string,
std::u16string, std::u32string, std::wstring, std::error_code , and
std::thread::id .

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #7
On 2008-05-31 17:50, Juha Nieminen wrote:
James Kanze wrote:
>I don't know about the "typically faster". Their average access
time is faster IF the hash function is good. Typically, I find
that it's not always that good (although the situation is
improving).

Question: Will the new C++ standard require for the libraries to
provide high-quality default hashing functions for internal types (and
perhaps some other standard types such as std::string), or will the user
be forced to always provide one himself?

Creating good-quality hashing functions are not a trivial task at all
(and the subject of continuing extensive research). One cannot expect
the average user to invent a good-quality function without extensive
knowledge and experience on the subject.
Currently the parametrised hash struct (which is used by the unordered
containers) is required to be instantiable for integers, float, double,
pointers, and string-types. It says nothing about the quality of the
implementation.

--
Erik Wikström
Jun 27 '08 #8
Pete Becker schrieb:
> Creating good-quality hashing functions are not a trivial task at all
(and the subject of continuing extensive research). One cannot expect
the average user to invent a good-quality function without extensive
knowledge and experience on the subject.

Indeed. That's why I've never thought that standardizing hashed
containers was a good idea. There's just too much flexibility, making
them hard to specify well, with the result that naive users can get
horrible performance without knowing why.

But, to answer your question, no, there is no requirement for "high
quality" hashing functions. Implementations will be required to provide
hashing functions for the builtin types, pointers, std::string,
std::u16string, std::u32string, std::wstring, std::error_code , and
std::thread::id .
What about std::pair<>, tuple<>, etc.?

How to do a good hashing function for a combined type like

struct key
{
int key1;
std::string key2;
};

?

--
Thomas
Jun 27 '08 #9
On 2008-05-31 12:42:50 -0400, "Thomas J. Gritzan"
<ph************ *@gmx.desaid:
Pete Becker schrieb:
>> Creating good-quality hashing functions are not a trivial task at all
(and the subject of continuing extensive research). One cannot expect
the average user to invent a good-quality function without extensive
knowledge and experience on the subject.

Indeed. That's why I've never thought that standardizing hashed
containers was a good idea. There's just too much flexibility, making
them hard to specify well, with the result that naive users can get
horrible performance without knowing why.

But, to answer your question, no, there is no requirement for "high
quality" hashing functions. Implementations will be required to provide
hashing functions for the builtin types, pointers, std::string,
std::u16string , std::u32string, std::wstring, std::error_code , and
std::thread::i d.

What about std::pair<>, tuple<>, etc.?
They're not on the list.
>
How to do a good hashing function for a combined type like

struct key
{
int key1;
std::string key2;
};

?
It depends strongly on how the values are distributed.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
2019
by: Pat | last post by:
I want to look for some one-to-one hashing function. In C++, any one-to-one hashing function?
1
3007
by: snowteo | last post by:
Hi,I have to do this exercises can you help me: 1)Write a program to implement exetendible hashing.If the table is small enough to fin in main memory,how does its performance compare with open and closed hasing? 2)A basic program consists of a series of statements,each of which is numbered in ascending order.Control is passed by use of a goto or gosub and a statement number.Write a program that reads in a legal BASIC program and renumbers...
11
3431
by: Wm. Scott Miller | last post by:
Hello all! We are building applications here and have hashing algorithms to secure secrets (e.g passwords) by producing one way hashes. Now, I've read alot and I've followed most of the advice that made sense. One comment I've seen alot about is "securing the hashing routine" but no-one explains how to accomplish this. So how do I secure my hashing routine? Do I use code access security, role based security, ACLs, etc or combination?...
10
2864
by: Dino M. Buljubasic | last post by:
Hi, I am using MD5 to hash my passwords and add them to database as hashed. I have noticed though that some passwords don't get recognized and I suppose that it happen because hashing might introduce some characters in my password that are not handled properly by SQL server then. For example, password 'startreck' works just fine password 'test' does not
19
3832
by: Ole Nielsby | last post by:
How does the GetHashCode() of an array object behave? Does it combine the GetHashCode() of its elements, or does it create a sync block for the object? I want to use readonly arrays as dictionary keys, based on their content, not their identity. Is this feasible using the arrays directly, or do I need to wrap them in a struct that handles GetHashCode and Equal? If so, is such a wrapper present in the standard class library?
8
4574
by: Maya | last post by:
Hello all, I'm using MD5 hashing in my application to give unique values to huge list of items my application receives, originally every item's name was difficult to use as an id for this item although its unique but because it had certain characters and variable lengths I ended up using MD5 hashing of the name.
6
2255
by: Jayender | last post by:
Hi, What is the difference between Hashing and Encryption ?
4
3399
by: wkatz | last post by:
Hi, Gurus. What hashing algorithm outputs hash value as numbers only? For example, if you pass a “John Q. Public” it will output 23324. If there is no such hashing, how hard is it to hire somebody to write a fairly quick one? It could be some fast hashing and then another function that creates numbers. Much obliged. wkatz.
1
4413
by: Tinku | last post by:
Hi friends I know Static Hashing and i know about Dynamic Hashing, still i have problem to make program with Dynamic Hashing I am new in "C" world, please help me, my problem is: i have to make program in Dynamic hashing i have to store int value in nodes user only enter int value by this value i have to find hash key and make symbol table my struct are
0
8808
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9316
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9177
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9077
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9021
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7954
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5951
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4465
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
3
2113
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.