Introduction to Hashing

Hashing is a method to store data in an array so that storing, searching, inserting and deleting data is fast. For this every record needs an unique key.The basic idea is not to search for the correct position of a record with comparisons but to compute the position within the array. The function that returns the position is called the 'hash function' and the array is called a 'hash table'.

Main idea: Use an array of size m and the key k as address of the array.
A hash function h is used to map keys to [0::m-1].
Key technical issues :
- What is a good h? A good function avoids (but does not eliminate)collisions, and is quick to compute.
- How do we resolving collisions? Retrieval time is a function of collisions.
- What if we run out of space in the table?
- Can we rearranging keys upon an insertion?

A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.A hash function may map two or more keys to the same hash value.Hash functions are related to (and often confused with) check sums,check digits, fingerprints, randomization functions, error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements and is designed and optimized differently.

A hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., person names) to associated values (e.g., their telephone numbers).n general, a hashing function may map several different keys to the same index. Therefore, each slot of a hash table is associated with (implicitly or explicitly) a set of records, rather than a single record. For this reason, each slot of a hash table is often called a bucket, and hash values are also called bucket indices.

RS422 Standard

RS-422 is a telecommunications standard for binary serial communications between devices. It is the protocol or specifications that must be followed to allow two devices that implement this standard to speak to each other. RS-422 is an updated version of the original serial protocol known as RS-232.

This standard was introduced in 1975 to offer improvements over the older RS-232 standard. It provides a balanced line with optional termination. The standard uses a voltage differential of 2v min to 5v max to represent the binary 0's and 1's. The specification allows data rates up to 10M baud at 40 feet maximum cable length.
The maximum cable length that can be driven will depend on the baud rate, the driver/receiver IC's, the cable type, and the amount of electrical noise in the surrounding environment. RS-422 can be used for point-to-point communication or for multi-drop one-master/many-slave systems.

The RS-422 standard only defines the characteristic requirements for the balanced line drivers and receivers. It does not specify one specific connector, signal names or operations. RS-422 interfaces are typically used when the data rate or distance criteria cannot be met with RS-232. The RS-422 standard allows for operation of up to 10 receivers from a single transmitter. The standard does not define operations of multiple tri-stated transmitters on a link.

RS-422 is a balanced four wire system. The signal sent from the DTE device is transmitted to the DCE device through two wires and the signal sent from the DEC device to the DTE device is transmitted through the other two wires. The signals on each pair of wires are the mirror opposite of each other, i.e., a "1" datum is transmitted as a plus 2 volt reference on one wire and a minus 2 volt reference on the other wire. To send a "0" datum, a minus 2 volt reference is transmitted through one wire and a plus 2 volt reference on the other wire. That is the opposite of what was done to transmit a \'1\' datum.

The RS-422-A interfaces between the Data Terminal Equipment (DTE) and Data Communication Equipment (DCE) or in any point-to-point interconnection of signals between digital equipment. It employs the electrical characteristics of balanced-voltage digital interface circuits.

RS485 Standard

RS-485 is a telecommunications standard for binary serial communications between devices. It is the protocol or specifications that need to be followed to allow devices that implement this standard to speak to each other. A RS-485 compliant network is a multi-point communications network. The RS-485 standard specifies up to 32 drivers and 32 receivers on a single (2-wire) bus. RS-485 drivers are now even able to withstand bus contention problems and bus fault conditions. A RS-485 network can be constructed as either a balanced 2 wire system or a 4 wire system. If a RS-485 network is constructed as a 2 wire system, then all of the nodes will have equal ranking. A RS-485 network constructed as a 4 wire system, has one node designated as the master and the remaining nodes are designated as slaves. The maximum cable length can be as much as 4000 feet because of the differential voltage transmission system used. The typical use for RS485 is a single PC connected to several addressable devices that share the same cable.

RS485 meets the requirements for a truly multi-point communications network, and the standard specifies up to 32 drivers and 32 receivers on a single (2-wire) bus. With the introduction of "automatic" repeaters and high-impedance drivers / receivers this "limitation" can be extended to hundreds (or even thousands) of nodes on a network. RS485 extends the common mode range for both drivers and receivers in the "tri-state" mode and with power off. Also, RS485 drivers are able to withstand "data collisions" (bus contention) problems and bus fault conditions.

SPECIFICATIONS RS485
- Mode of Operation DIFFERENTIAL
- Total Number of Drivers and Receivers on One Line 1 DRIVER & 32 RECEIVER
- Maximum Cable Length 4000 FT.
- Maximum Data Rate 10Mb/s
- Maximum Driver Output Voltage -7V to +12V
- Driver Output Signal Level (Loaded Min.) Loaded +/-1.5V
- Driver Output Signal Level (Unloaded Max) Unloaded +/-6V
- Driver Load Impedance (Ohms) 54
- Max. Driver Current in High Z State Power On +/-100uA
- Max. Driver Current in High Z State Power Off +/-100uA
- Slew Rate (Max.) N/A
- Receiver Input Voltage Range -7V to +12V
- Receiver Input Sensitivity +/-200mV
- Receiver Input Resistance (Ohms) >=12k

RS232 Standard

RS232 is a asynchronous serial communication protocol widely used in computers and digital systems. It is called asynchronous because there is no separate synchronizing clock signal as there are in other serial protocols like SPI and I2C.
In RS232 there are two data lines RX and TX. TX is the wire in which data is sent out to other device. RX is the line in which other device put the data it need to sent to the device.
Voltage levels in RS232 are HIGH=-12V and LOW=+12V.

RS-232 Specifications :
- Cabling : Single-ended
- Number of Devices : 1 transmit, 1 receive
- Communication Mode : Full duplex
- Distance(max) : 50 feet at 19.2kbps
- Data Rate(max) : 1Mbps
- Signaling : Unbalanced
- Mark(data 1) : -5V (min) -15V (max)
- Space(data 0) : 5V (min) 15V (max)
- Input Level(min) : ±3V
- Output Current : 500mA
- Impedance : 5kW (Internal)
- Bus Architecture : Point-to-Point

RS232 Data Transmission :
Transmission
1. When there is no transmission the TX line sits HIGH (STOP CONDITION).
2. When the device needs to send data it pulls the TX line low for 104uS (This is the start bit which is always 0).
3. Then it sends each bit with duration of = 104uS.
4. Finally it sets TX lines to HIGH for at least 104uS (This is stop bit and is always 1).
Reception :
1. The receiving device is waiting for the start bit i.e. the RX line to go LOW.
2. When it gets start bit it waits for half bit time i.e. 104/2 = 51uS, i.e.it is in middle of start bit, it reads it again to make sure it is a valid start bit and not a spike.
3. Then it waits for 104uS and now it is in middle of first bit. It then reads the value of RX line.
4. In the same way it reads all the 8 bits.
5. Now the receiver has the data.

Limitations of RS232 Standard :
* The large voltage swings and requirement for positive and negative supplies increases power consumption of the interface and complicates power supply design. The voltage swing requirement also limits the upper speed of a compatible interface.
* Single-ended signaling referred to a common signal ground limits the noise immunity and transmission distance.
* Multi-drop connection among more than two devices is not defined. While multi-drop "work-arounds" have been devised, they have limitations in speed and compatibility.
* Asymmetrical definitions of the two ends of the link make the assignment of the role of a newly developed device problematic; the designer must decide on either a DTE-like or DCE-like interface and which connector pin assignments to use.
* The handshaking and control lines of the interface are intended for the setup and takedown of a dial-up communication circuit; in particular, the use of handshake lines for flow control is not reliably implemented in many devices.
* No method is specified for sending power to a device. While a small amount of current can be extracted from the DTR and RTS lines, this is only suitable for low power devices such as mice.
* The 25-way connector recommended in the standard is large compared to current practice.

Data Communication Modes

Today computer is available in many offices and homes and therefore there is a need to share data and programs among various computers with the advancement of data communication facilities. The communication between computers has increased and it thus it has extended the power of computer beyond the computer room. Now a user sitting at one place can communicate computers of any remote sites through communication channel.

In data communication four basic terms are frequently used. They are :
* Data: A collection of facts in raw forms that become information after processing.
* Signals: Electric or electromagnetic encoding of data.
* Signaling: Propagation of signals across a communication medium.
* Transmission: Communication of data achieved by the processing of signals.

There are three ways for transmitting data from one point to another :
- Simplex :Data only flows in one direction.A good example of simplex
communications is a radio station and your car radio. Simplex is not often
used in computer communications because there is no way to verify when or if data is received. However, simplex communications is a very efficient way to distributed vast amounts of information to a large number of receivers.
- Half Duplex : In this mode, devices allow both transmission and receiving, but not at the same time. Essentially only one device can transmit at a time while all other half-duplex devices receive. RS-485 works in half-duplex mode.
- Full Duplex : In this mode, devices can transmit and receive data at the same time. RS232 and RS422 are examples of Full Duplex communications. There are separate transmit and receive signal lines that allow data to flow in both directions simultaneously.

Difference between buffer and cache ?

A buffer is a region of memory used to temporarily hold output or input data.Buffers can be implemented in either hardware or software, but the vast majority of buffers are implemented in software. Buffers are used when there is a difference between the rate at which data is received and the rate at which it can be processed.

The terms "buffer" and "cache" are not mutually exclusive and the functions are frequently combined; however, there is a difference in intent. A buffer is a temporary memory location, that is traditionally used because CPU instructions cannot directly address data stored in peripheral devices. Thus, addressable memory is used as intermediate stage.

Additionally such a buffer may be feasible when a large block of data is assembled or disassembled (as required by a storage device), or when data may be delivered in a different order than that in which it is produced. Also a whole buffer of data is usually transferred sequentially (for example to hard disk), so buffering itself sometimes increases transfer performance. These benefits are present even if the buffered data are written to the buffer once and read from the buffer once.

A cache also increases transfer performance. A part of the increase similarly comes from the possibility that multiple small transfers will combine into one large block. But the main performance-gain occurs because there is a good chance that the same datum will be read from cache multiple times, or that written data will soon be read. A cache's sole purpose is to reduce accesses to the underlying slower storage. Cache is also usually an abstraction layer that is designed to be invisible from the perspective of neighboring layers.

Page/Disk Cache and Web Cache

PAGE CACHE :
Page Cache or disk cache is transparent buffer of disk-backed pages kept in main memory (RAM) by the operating system for quicker access. All memory that is not directly allocated to applications is usually utilized for page cache. Since non-dirty pages in the page cache have identical copies in secondary storage(hard disk), discarding and re-using their space is much quicker than paging out application memory, and is often preferred.The page cache also aids in writing to a disk. Pages that have been modified in memory for writing to disk, are marked "dirty" and have to be flushed to disk before they can be freed. When a file write occurs, the page backing the particular block is looked up. If it is already found in cache, the write is done to that page in memory. Otherwise, when the write perfectly falls on page size boundaries, the page is not even read from disk, but allocated and immediately marked dirty. Otherwise,the page(s)are fetched from disk and requested modifications are done.

WEB CACHE :
Web caching is the caching of web documents(e.g.,HTML pages, images) to reduce bandwidth usage, server load, and perceived lag. A web cache stores copies of documents passing through it; subsequent requests may be satisfied from the cache if certain conditions are met.
With a local cache in operation, user web object requests go via the local cache which then retains a copy of the said web object. This results in all subsequent requests for the same object being fulfilled from the local cache instead of from the site of origin. This process of web caching minimizes the amount of times identical web objects are transferred from remote websites by retaining copies of requested URLs in a cache. A web cache can be installed utilizing both software and hardware, and can run on various different platforms.
With a local cache in operation, subsequent requests for previously cached URLs result in the cached copy of the object being returned to the user; creating little or no extra network traffic, improving efficiency and reducing waiting time.