473,847 Members | 1,707 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How to implement a Hash Table in C

Hi
can anybody tell me that which ds will be best suited to implement a
hash table in C/C++

thanx. in advanced

Aug 11 '07
139 14269
Malcolm McLean wrote:
"Richard Heathfield" <rj*@see.sig.in validwrote in message
.... snip ...
>
>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.
Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Aug 18 '07 #101

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...
Malcolm McLean wrote:
>"Richard Heathfield" <rj*@see.sig.in validwrote in message
... snip ...
>>
>>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read. Purely syntactical. The indirection operator happens to
be the same as a multiply. All functions take parentheses, except sizeof,
which is a function in the sense that matters - it retuns a value based on
its argument, but not of course in terms of generated code. So you've got
two quirks in one expression.

In compiler terms t is better, of course, because if you change ptr's type
the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Aug 18 '07 #102

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...
Flash Gordon wrote:
>Malcolm McLean wrote, On 18/08/07 10:58:
... snip ...
>>
>>Criticisms have been made, some of them indisuptable bug reports,

For which you have not published an errata so that your audience
know about them.

For contrast, look at my hashlib. It was published complete with
the test suite and test programs that evaluated it during and after
development. I have had two and a half bug reports since the
initial publication, and no more for years.
And there was one I found in Dann's recommended text, admittedly in a code
fragment, and one in Ben Pfaff's circular buffer. Two in my two hash
tables, though one could be described as a feature. So assuming
Poisson-distributed bugs, we're doing about equally. However I am blamed.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Aug 18 '07 #103
Malcolm McLean said:
>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...
>>
<snip>
>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read.
Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 18 '07 #104
Richard Heathfield wrote:
Malcolm McLean said:
>>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******* ********@yahoo. com...
>>>

<snip>
>>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read.

Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.
To be honest this construct threw me the first time I encountered it, which
is of course in clc, but it hasn't bothered me in the slightest after I
looked it up in the FAQ.

C's expressions have to be understood with C's rules and quirks in mind, not
by comparing them to mathematical expressions. I suppose someone new to C
will find it a bit strange, but then this is true for almost all
programming languages. There's a reason they are not classified under the
natural languages class.

Aug 18 '07 #105
CBFalconer wrote, On 18/08/07 19:40:
Malcolm McLean wrote:
>"Richard Heathfield" <rj*@see.sig.in validwrote in message
... snip ...
>>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.
Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
Unless you need enough space for two objects ;-)

Unsurprisingly, I agree with you on this.
--
Flash Gordon
Aug 18 '07 #106
"Malcolm McLean" <re*******@btin ternet.comwrite s:
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...
>Malcolm McLean wrote:
>>"Richard Heathfield" <rj*@see.sig.in validwrote in message
... snip ...
>>>
His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable( ) function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read. Purely syntactical. The indirection operator
happens to be the same as a multiply. All functions take parentheses,
except sizeof, which is a function in the sense that matters - it
retuns a value based on its argument, but not of course in terms of
generated code. So you've got two quirks in one expression.
No, sizeof is not a function. It's a unary operator, just like "-",
"*", and "&". (If "sizeof" is a function in some abstract sense, then
so is "-", but C doesn't call them functions.) The confusion is
probably caused by the fact that it's the only operator whose symbol
look like an identifier rather than punctuation.

Pretend that 'sizeof' had been spelled '$', and you'll see what I mean.

But if you find
ptr = malloc(sizeof *ptr);
too confusing because it looks too much like a multiplication, you can
write
ptr = malloc(sizeof(* ptr));
applying the operator to a parenthesized expression.
In compiler terms t is better, of course, because if you change ptr's
type the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.
The real issue is that the clc-approved form (a) is perfectly
understandable once it's explained (something you could do in your
book if you chose), and (b) makes maintenance easier, because you
don't have to keep the target type and the size expression
synchronized manually (with no warning from the compiler if you get it
wrong).

You're right that 'ptr = malloc(sizeof *ptr)' is not common. That's a
pity, because it's *better* than the alternatives, and you have an
opportunity to help teach that.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 18 '07 #107
Malcolm McLean wrote, On 18/08/07 22:02:
>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...
>Malcolm McLean wrote:
>>"Richard Heathfield" <rj*@see.sig.in validwrote in message
... snip ...
>>>
His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable( ) function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read.
A lot of newbies here don't find it hard once it is pointed out to them.
Purely syntactical.
Only if you consider "ptr = malloc(sizeof(t ype))" to be purely syntactical.

The indirection operator happens
to be the same as a multiply.
I very much doubt that people would mistake it for being multiplication
in this usage.
All functions take parentheses, except
sizeof, which is a function in the sense that matters - it retuns a
value based on its argument, but not of course in terms of generated
code.
It is only a function in the same sense that a unary minus is a
function. It has one operand and yields a result. The lack of
parenthesis in the "clc recommended" form if anything make it clearer it
is not a function.
So you've got two quirks in one expression.
You have more quirks than that.
In compiler terms t is better, of course, because if you change ptr's
type the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.
Most of the regulars here have a good few years of experience in
maintaining code written by themselves and others. I personally also
have experience of passing code on (not C code) to be maintained by
others and still being around myself to here what their issues are. So I
think many of us have reason to believe we *do* understand what the
maintainability issues are, and many of us disagree with you on this.
--
Flash Gordon
Aug 18 '07 #108
Richard Heathfield wrote:
>
Malcolm McLean said (in reply to me):
malloc( sizeof *ptr) is a bad clc ism

No, it's a good clc-ism.
(ptr = malloc(N * sizeof *ptr)) is an absolutely great expression;
I use it much.
that you will seldom see in another environment.

Right. As Sturgeon says, at least 90% of everything is crud, so you'd
expect to find malloc(sizeof *ptr) in only 10% of cases (or fewer).
That doesn't mean it's bad. It just means most people haven't come
across it yet.
The reader has to perform a mental dereference which makes it harder
to see if the size of correct.

If the reader has to perform a mental dereference, he (or she) doesn't
understand sizeof. No dereferencing occurs, because sizeof does not
evaluate its argument. Furthermore, the size is *bound* to be correct
for any object pointer type.
For strings, I frequently call malloc this way:
char *string = malloc(length + 1);

--
pete
Aug 18 '07 #109
Richard Heathfield <rj*@see.sig.in validwrites:
Malcolm McLean said:
>>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******* ********@yahoo. com...
>>>

<snip>
>>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.
It's hard to read.

Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.

<snip>
IMO, It is fairly uncommon to see

(sizeof *p)

in legacy code bases and is at odds with "normal" C operators as was
well described by Keith in another post in this thread. I think MM has
a point.

The people reading his algorithms shouldn't need to be C experts to
understand his code.

But don't let that stop you taking another opportunity to proclaim your
genius.
Aug 18 '07 #110

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

Similar topics

2
1375
by: Yat | last post by:
I want to use hash table in C. Have any build-in library in C so that I can use it without implement hash table myself? Thx
24
4323
by: kdotsky | last post by:
Hello, I am using some very large dictionaries with keys that are long strings (urls). For a large dictionary these keys start to take up a significant amount of memory. I do not need access to these keys -- I only need to be able to retrieve the value associated with a certain key, so I do not want to have the keys stored in memory. Could I just hash() the url strings first and use the resulting integer as the key? I think what I'm...
0
9886
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
10983
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
10647
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...
0
10338
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
7056
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
5911
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4528
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4119
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3164
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.