Jump to content

Basics of Hash Tables


Tutorial

Recommended Posts

Tutorial by KingTomato

 

What is a hash table?

A dictionary in which keys are mapped to array positions by a hash function. Having more than one key map to the same position is called a collision. There are many ways to resolve collisions, but they may be divided into open addressing, in which all elements are kept within the table, and chaining, in which additional data structures are used.

 

Well, what's that all mean? Well to put it bluntly, it means a set of data stored in RAM (Random Access Memory) allowing for quick and easy access (quick being the opperative term). With a hash table, you can store hundreds (if not thousands) of data entries and retreive it in a matter of seconds (or less).

 

How do I make a hash table?

Well, to make a hash table you first must have some idea of how much data you will be storing in it. The average size of the hash table is the square root of the number of entries you expect to hold. So if you plan on 100 entries, a size of 10 should be sufficient. Here is the syntax (or basic layout) of how the /hmake command works.

 

/hmake <name> <size>

 

As we move along, I will try to apply the different commands used with hash tables in a demonstration script. This is both to show what we are talking about, and to show how you would apply it in a script. For my example, I will choose the all-too-popular acronym script.

 

Thus far, we have seen how we make a hash table, so now lets apply. A good assumption for our acronym scripts would be we want to create the hash table every time we load mIRC. To do this we will add the /hmake command in an on Start event.

 

on *:START: {
; create the hash table of 100 items (size of 10)
 /hmake acronym 10
}

 

I know how to make a hash table, now how do I put information in it?

Storing information is just as easy as creating the table to store it in. For this, we turn to the /hadd command. The syntax for this command is as follows:

 

/hadd <table> <data_name> <value>

 

So in our example, when we want to add the acronyms and their values to the table. For this, lets create an alias that is only used for the first initialization of the acronym hash table. Our code will be as follows:

 

alias acronym.init {
; add the values to our table
 /hadd acronym afk Away From Keyboard
 /hadd acronym brb Be Right Back
 /hadd acronym gtg Got To Go
 /hadd acronym lol Laughing Out Loud
 /hadd acronym ttyl Talk To You Later
}

 

Okay, so now we have the table created, and the initializing alias made. Before we get to intializing it, lets look at loading and saving the hash table. You'll see why I feel this is next in the order of operations in just a second.

 

How do I save or load a hash table?

Saving and loading hash tables is very straight forward. The load/save commands are as follows:

 

/hload <table> <filename>
/hsave <table> <filename>

 

Okay, well lets talk about loading first. Say we want to take a hash table file, and load it into our table. Now, for us to do this we first need to know which file. For our example we have been following, lets use the filename "acronyms.hsh" (.hsh for hash extention). Now, to load this file we will be using the command /hload acronym acronyms.hsh.

 

Saving the hash table is just as easy. For this tutorial, we will save it in plain text format and not in binary. So do this we will use /hsave -o acronym acronyms.hsh. Now you may be wondering why the -o is there. The -o is simply to tell mirc to overwrite the prexisitng hash table file (if any) with our new data. Simple, right?

 

There is one more very important command that I dont want to exclude while we are on the topic, but we will get to it later. This command is /hfree. /hfree will free the memory of a hash table after you kill it, so that the memory now being used itsn't taking up space. This is very useful if you only need a hash table for a short while, for example some people chose to use them for clone scanners for very large channels. Again, we will get to this a command soon, but for now here is the syntax:

 

/hfree <table>

 

Now, lets apply the load and save commands to our example while it is fresh in our mind. So far in our example we know how to make the hash table when mirc starts up, and how to add things to our table with an alias thats not being called--yet. Now to apply all the things we've learned we use the on start event again. First we will make the hash table. Next, we will check if a hash table has been saved as acronyms.hsh. If it has, we load it, otherwise we will call our alias and save our new table (hopefully my order of operations was appropriate).

 

on *:START: {
; create the hash table of 100 items (size of 10)
 /hmake acronym 10
; Load our hash file if it's there, other wise initialize the hash table
 if ($isFile(acronyms.hsh)) {
  ; file exists, now we load it
   /hload acronym acronyms.hsh
 }
 else {
  ; the file does not exist.  Now we initialize, and save
   /acronym.init
   /hsave -o acronym acronyms.hsh
 }
}

 

Now we have the create, add, load and save done. Now you will notice I saved after adding the new entried to the hash table, but what if we add more? Well, now we move on to on Exit event. While we are adding this, lets also apply the /hfree command to after we save our table, so we can free up the memory the table is using before exiting mirc. Here is what it would look like:

 

on *:EXIT: {
; save our table on exit
 /hsave -o acronym acronyms.hsh
; clear the used memory
 /hfree acronym
}

 

 

Okay, I have my table with the information--now how do I access it?

Accessing the information is the hash table is as simple as pi (yes, i mean pi). This is where the $hget and $hfind identifiers come in. Lets begin with the former, shall we?

$hget is a simple identifyer, and a very useful one at that. With this identifier you can deturmine if a hash table exists, find if a hash entry exists, and get the value associated with the entry. The first, deturmining if a hash table exists, is the simplest task. Simply use $hget(

) to find this out.

 

Ex:

if ($hget(acronym)) /echo -a Acronym Table Exists!
Now, to get an entry, just use $hget(<table>, <entry>).

 

Ex:

if ($hget(acronym, lol)) /echo -a lol is in the table!

 

And finally getting the value.

var %meaning = $hget(acronym, lol)

But wait, we just used that last one for checking if an entry exists, whats the difference? Simply put, when you use $hget to check if an entry exists, all your checking for is if the value associated with the entry exists, and thats what the if statement did. When passed a value, if the value is not null or 0, it will return true. What you do have to watch out for is if an entry containg the number 0, because that will trigger a false.

 

Ex:

/hadd myTable a 0
if ($hget(myTable, a)) /echo -a a exists!
else /echo -a a doesn't exist!

 

Watch out, the above code will produce "a doesn't exist!". This is simply because the value of a is a 0, which is also considered a false for mIRC. For a more failsafe way, you may choose to use:

/hadd myTable a 0

if ($hget(myTable, a) != $null) /echo -a a exists!

else /echo -a a doesn't exist!

With the != $null addition, you can now be sure it will return true if anything is in the a value.

Moving on with retrieving data, we have $hfind. $hfind is a more advanced version of $hget in thtat is also accepts wildcard matches, and has the ability to search not only entries, but values in entries. This means that you can search for not only "lol", but also "Laughing Out Loud" and it will return "lol". In order to search tthrough data though, you must specifty the .data property. So as I just mentioned, looking for the entry "lol" would look something like this:

 

var %entry = $hfind(acronym, Laughing Out Loud, 1).data

 

The above code would assign %entry the value of "lol".

Now, how to apply this in our example. For this, we will be using the on Input event to "Catch" the acronyms as they are typed and sent to the server. We will do a search through the text for the acronyms we wish to replace, replace them, then send the message.

 

on *:INPUT:#: {
; first make sure the text entered isn't a command
 if ($left($1, 1) !isin $+(/,$readini($mircini, text, commandchar))) {
  ; search for words to replace
   var %w = 1              |; current word we're comparing
   var %text               |; current message
   var %acro = [<acronym>] |; the design you want your acronym to take
  ; loop through each word looking through a match
   while ($gettok($1-, %w, 32) != $null) { |; we include != $null incase the user types a 0
     var %word = $ifmatch
    ; find the word in our table
     if ($hget(acronym, %word) != $null) var %text = %text $replace(%acro, <acronym>, $ifmatch)
     else var %text = %text %word
    ; Increase Counter Variable
     /inc %w
   }
  ; send the message to the channel
   /msg $chan %text
  ; stop the "double talk"
   /halt
 }
}

 

 

The complete code

Now we have the events to create and add to the table, save the table, and use the table. With this information, lets piece it all together. The following is all the different parts of the code grouped together into one addon. Everything is still fully commented to that you can look at it and not have to second guess what's going on.

 

; initialize the first few acronyms
alias acronym.init {
; add the values to our table
 /hadd acronym afk Away From Keyboard
 /hadd acronym brb Be Right Back
 /hadd acronym gtg Got To Go
 /hadd acronym lol Laughing Out Loud
 /hadd acronym ttyl Talk To You Later
}

; Intiilize the table
on *:START: {
; create the hash table of 100 items (size of 10)
 /hmake acronym 10
; Load our hash file if it's there, other wise initialize the hash table
 if ($isFile(acronyms.hsh)) {
  ; file exists, now we load it
   /hload acronym acronyms.hsh
 }
 else {
  ; the file does not exist.  Now we initialize, and save
   /acronym.init
   /hsave -o acronym acronyms.hsh
 }
}

; Save the table
on *:EXIT: {
; save our table on exit
 /hsave -o acronym acronyms.hsh
; clear the used memory
 /hfree acronym
}

; replace acronyms with their proper meaning
on *:INPUT:#: {
; first make sure the text entered isn't a command
 if ($left($1, 1) !isin $+(/,$readini($mircini, text, commandchar))) {
  ; search for words to replace
   var %w = 1              |; current word we're comparing
   var %text               |; current message
   var %acro = [<acronym>] |; the design you want your acronym to take
  ; loop through each word looking through a match
   while ($gettok($1-, %w, 32) != $null) { |; we include != $null incase the user types a 0
     var %word = $ifmatch
    ; find the word in our table
     if ($hget(acronym, %word) != $null) var %text = %text $replace(%acro, <acronym>, $ifmatch)
     else var %text = %text %word
    ; Increase Counter Variable
     /inc %w
   }
  ; send the message to the channel
   /msg $chan %text
  ; stop the "double talk"
   /halt
 }
}

 

And there we go. Now we have a hash table that is used to replace acronyms. Its a simple script, but is a nice little beginner's starting point. Hope this helps!

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
×
×
  • Create New...