Posts Tagged ‘hash’

A first BD-incollo screenshot, report after 48 hours

Friday, September 26th, 2008

Time for a screenshot! This is the page which handles new pastes:

BD-incollo: page for new pastes

BD-incollo: page for new pastes


There are some news:

  • I implemented a hash function (hexadecimal number as output) to be used to access pastes, instead of using their ids
  • I played with templates to have all the functionalities accessed in very small mouse movements

Next, the requirements regarding automatic cleanup of the pastes!

  • Share/Save/Bookmark

Tags: , , , , , , , , ,
Posted in Activism?, Free*, Programming | No Comments »

Hash Maps with linear probing and separate chaining

Monday, April 28th, 2008

Time for two new C programs! At the DSA course I learned something about Hash Tables and collision resolutions.
I just implemented insert/search/print operations.

The first source code is an implementation of a Hash Map with open addressing (linear probing) as collision resolution method.
The following are the interesting functions of the program. As always, take a look at the source code for comments:

// hashMapLinear[] is the hash map
void linearProbingInsert(int value){
    int probe = hash(value);
    while (hashMapLinear[probe]!=0){                            
        probe = fmod((probe+1),SIZE_HASH_MAP);
    }
    hashMapLinear[probe] = value;
}

int linearProbingSearch(int value){
    int probe = hash(value);  
    int i;
    for(i=0;i<size_hash_map ;i++){    
        if(hashMapLinear[probe]==value)
            return TRUE;                            
        probe = fmod((probe+1),SIZE_HASH_MAP);              
    }
    return FALSE;                                          
}
 

Download: hash-map-linear-probing.c

The second program is an implementation of a Hash Map with chaining as collision resolution method.
Interesting functions:

// t_hashTableNode is a struct that is created as single linked list
void chainedHashInsert(int value){
    int probe = hash(value);                        
    if(hashMapChained[probe] == NULL){          
        hashMapChained[probe] = malloc(sizeof(t_hashTableNode));
        hashMapChained[probe]->value = value;
        hashMapChained[probe]->next = NULL;
    }else{
        t_hashTableNode *hashTableNode = hashMapChained[probe];
        while(hashTableNode->next!=NULL){
            hashTableNode = hashTableNode->next;
        }
        hashTableNode->next = malloc(sizeof(t_hashTableNode));
        hashTableNode->next->value = value;
        hashTableNode->next->next = NULL;
    }
}

int chainedHashSearch(int value){
    t_hashTableNode *hashTableNode = hashMapChained[hash(value)];
    while(hashTableNode!=NULL){
        if(hashTableNode->value==value){
            return TRUE;
        }
        hashTableNode = hashTableNode->next;
    }
    return FALSE;
}
 

Download: hash-map-chaining.c

  • Share/Save/Bookmark

Tags: , , , , , , , , , , , , , , , , , ,
Posted in Programming | No Comments »