Reading: Hash Tables (K&R 6.5-6.6)

Reading: K&R 6.5-6.6

Please submit a question by 9 p.m. on Sunday, 1 May 2011.

Hash Tables

Ok, from what I understand from the reading, hash (char *s) returns an unsigned int, derived from the string s, and the value hash (s) is the index of the table entry that holds the value of s. But hash (s) returns hashval % HASHSIZE, so what happens if the hashvalue for str1 == HASHSIZE, and the hashvalue for str2 ==2* HASHSIZE? That is, hash (str1) could equal ,code>hash (str2), even when str1 and str2 are different. Either hash (s) must be unique for each s, or I'm misunderstanding how hash is used.

It's impossible to make hash (s) different for each s. Hence, we put a linked list of name/defn pairs in each cell, rather than just one name/value pair.

What the purpose of hash?

The algorithm is a hash-search - the incoming name is converted into a small non-negative integer, which is then used to index into an array of pointers. Hash does the conversion from name to small non-negative integer.

Trees

Is there a way to read this binary tree and obtain the sentence we started with?

No. We've rearranged the information for other purposes. Just like you can't unsort an array back to the original, you can't go from a tree of counts back to the original sentence.

What does it mean for a tree to be unbalanced?

One side (subtree) has many more nodes than the other.

Sam's obnoxious answers

What does strdup do?

man strdup

When would you use a hash table?

When would install or lookup be most useful?

In the example that K&R gave: When you're translating macros. In the implicit way: When you want to go from a word to its definition.

Is talloc a built-in function?

No. That's why K&R define it. That's why you don't get information back when you type man talloc.

Is it ok to think a node is like part of a string?

No. A node is like a node. (That is, like the nodes we've been putting in our linked lists for the past two weeks.)

I dont understand why we would want to represent data this way.

Which way?

Questions left to answer

Looking at the code at the bottom of page 140, what is going on here? If main has no parameters, what tree is being looked at, and how is that tree being created?

p->left = p->right = NULL;

This is adding the null pointer to the next sublevel of the tree when a new node is added, right? I'm confused about what specifically -> does."

Could you explain the relationships and differences between the malloc, talloc, and calloc functions?

I'm confused by the code for talloc. How can malloc be called with the parameter sizeof(tnode) if you're in the process of allocating memory for t-node?

Is the purpose of the hash function to assign strings an numeric index to be used in the hash table?

What determines what a good hash size is? Are there any disadvantages to having a really large hash size besides memory allocated to the pointers in the original pointer array?

Although I read the reading and I don't completely understand it, I have no questions.

The install function is pretty confusing. could we go through how it works in class?

How is talloc different from malloc and calloc?

What's the point of using strdup?

Wow "typedef" kind of blows my mind. I think it is a very cool concept but can't quite see that much use for it. Besides the example given in the book, can you show us some other examples or maybe explain if it is that useful?

Is p->left similar to how you have p->next?

I also do not understand how the hash value programs work. The program to put a value in the hash table is confusing. if ((np->defn==strdup(defn)) ==NULL), What does that do?"

Can you explain this code?

struct tnode *talloc(void);
char *strdup(char *);
/* addtree: add a node with w, at or below p */
struct treenode *addtree(struct tnode *p, char *w)
{
  int cond;
  if (p == NULL) { /* a new word has arrived */
    p = talloc(); /* make a new node */
    p->word = strdup(w);
    p->count = 1;
    p->left = p->right = NULL;
  } else if ((cond = strcmp(w, p->word)) == 0)
    p->count++; /* repeated word */
  else if (cond < 0) /* less than into left subtree */
    p->left = addtree(p->left, w);
  else /* greater than into right subtree */
    p->right = addtree(p->right, w);
  return p;
}