Conclusion I've reached about hash tables in C.

This is a discussion on Conclusion I've reached about hash tables in C. within the C Programming forums, part of the General Programming Boards category; Okay, just one conclusion. I need a math tutor. I cannot for the life of me calculate the worst case ...

  1. #1
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195

    Conclusion I've reached about hash tables in C.

    Okay, just one conclusion. I need a math tutor. I cannot for the life of me calculate the worst case scenarios when either increasing or inserting an element into a hash table. I won't even cover the whole probability thing. If anyone lives like within 10 miles of UC-Berkeley, email me.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    Try google.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    I was thinking about maybe trying LSD in an effort to bootstrap myself further. Yeah, google did help (sort of).

    http://groups.google.com/group/comp....3b014a9abaceaf

  4. #4
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Or Wikipedia. And FTLOG, read up on the other CS tutorials there. Free tutor.

    If you don't want to learn, there is no shortcut. A greek mathematician once told a king: "There is no royal road to geometry." Meaning: start learning yourself the hard way like we all did, or don't bother at all. Nobody's gonna drive all the way to your house and help you pass your CS course for you.

    Depends on your collision resolution policy. A good double hashing algorithm (eg. p-2 modular or quadratic search) typically leads to near-constant times.

    Of course, the worst-case is only bounded by the size of your hash table. Yes, no matter how you build it. It would be much more worthwhile to measure the amortized complexities of hashing algorithm implementations.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Iterable hash tables
    By OnionKnight in forum Tech Board
    Replies: 5
    Last Post: 07-21-2008, 02:02 AM
  2. developing hash tables in the C Programming language
    By w108dab in forum C Programming
    Replies: 1
    Last Post: 05-20-2008, 11:20 AM
  3. need help with hash tables with direct chaining
    By agentsmith in forum C Programming
    Replies: 4
    Last Post: 01-05-2008, 03:19 AM
  4. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  5. Problems with Hash Tables
    By Zildjian in forum C Programming
    Replies: 6
    Last Post: 11-06-2003, 07:53 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21