Computers store data in a data structure. Computer scientists write algorithms to access data from a data structure. It's good practice to use relevant data structure based on your need. It's good to have a wide perspective on variety of data structures in order to choose an appropriate data structure for your need. Inappropriate selection of data structure tends to increase data access time, no matter how powerful computer you might have!
Array, Lists, Tree and Hash are some of the basic data structure commonly used. Each of these are suitable for one or the other purpose. Stack, queue and graph can be termed as Abstract data types since underlying implementation can use from any suitable basic data structure. For example, Stack can be based upon an Array or a Linked List.
Hash becomes handy when it is required to have frequent and quick data access and when data modification/deletion is not so frequent. The idea behind hash is to have [ key : value ] pairs stored in a data structure. Multiple values can be stored for each key in a hash. Let's look at how data is stored and accessed from a hash.
Hash takes two values: 1) input data 2) input value. First, hash function converts "Input data" to a key. The generated key than indicates the location to store corresponding "input value". These locations are often called as "buckets". Multiple "input data" can fall into same buckets and hence one key can have multiple associated values.
For accessing data from a hash, we again provide "input data" to get corresponding "input value" stored in a hash. Given an "input data", hash applies the hash function which returns the key indicating the location where corresponding value was stored. Hash than accesses that bucket location and returns the corresponding stored value. In case when multiple values are stored for a given key, a comparison function has to be used in order to get right "input value" for given "input data".
Hash operations are quite efficient and provides O(1) access time for read/write/delete for best case and O(n) access time for worst case where "n" refers to number of items in a hash.
An example where hash can be used is as below:
Consider an application which wants to retrieve a person's phone number in no time given a name. A hash can be generated for [ name : phone-number ] pairs where name is a key and phone-number is a corresponding value. Now whenever we want to find a person's phone number, we can feed in that person's name to application returning his/her phone-number immediately, if found in O(1) time. This can be useful when say we data for millions of people in our database and we want a quick access to give person's phone-number.
Click here to watch an excellent video on Hash data structure.
An example where hash can be used is as below:
Consider an application which wants to retrieve a person's phone number in no time given a name. A hash can be generated for [ name : phone-number ] pairs where name is a key and phone-number is a corresponding value. Now whenever we want to find a person's phone number, we can feed in that person's name to application returning his/her phone-number immediately, if found in O(1) time. This can be useful when say we data for millions of people in our database and we want a quick access to give person's phone-number.
Click here to watch an excellent video on Hash data structure.
Your post was very nicely written. Your general description of data structures can be a great help to those that are not familiar with data structures. Your in-depth description of the Hash data structure was well thought out and very informative. It was informative and technical without being too technical that someone that is not familiar with it could still understand it. I notice a couple of grammatical errors that a reread should allow you to catch them. Aside from that, great post!
ReplyDeleteNice post Mehal. Great introduction to your discussion on Hashes. Your description was easy to read and very informative with a good practical example of how a hash structure could be used. Hashes can also be used for error checking and authentication. In error checking a hash is used to check downloaded data to insure the file received is the same. For authentication purposes hashes are used as a security measure to authenticate messages and insure original input.
ReplyDeleteYou may want to provide a link or two to your sources.
ReplyDeleteAwesome blog. This is exactly what I want to see from a blog. you go in-depth on a focused topic and give a quick, simple explanation of it. I love reading blogs where I can learn about computer science and anything of interest to me in general easily and this is one of them. Hashes are really cool because you can makes programs much more efficient by scrambling the input basically. Hashes are not only used for data structures but they are also a major component of information security. The hash functions for security are quite a bit more complex as they have to be security sensitive while the hash functions for data are simple for efficiency. The blog could have used some sources so I could go in even more depth on the topic if I wanted to.
ReplyDelete