Skip to main content

Algorithm: Hash Tables

If keys are small integers, we can use an array to implement a symbol table, by interpreting the key as an array index so that we can store the value associated with key i in array position i.

Search algorithms that use hashing consist of two separate parts. The first step is to compute a hash function that transforms the search into an array index. Ideally, different keys would map to different indices. This ideal is generally beyond our reason, so we have to face the possibility that two or more different keys may hash to the same array index. Thus, the second part of a hashing search is a collision-resolution process that deals with this situation.

Hash Functions. If we have an array that can hold M key-value pairs, then we need a function that can transform any given key into an index into that array:an integer in the range[0,M-1]. We seek a hash function that is both easy to compute and uniformly distributes the keys.

The most commonly used method for hashing integers is called modular hashing. We choose the array size M to be prime, and for any positive integer key k, compute the remainder when diving k by M. This function is very easy to compute(k%M, in Java), and is effective in dispering the keys evenly between 0 and M-1.

Modular hashing works for long keys such as strings. too: we simply treat them as huge integers. For example, the code below computes a modular hash function for a String s.

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R*h + s.chartAt(i)) %M;

Java Conventions. Java helps us address the basic problem that every type of data needs a hash function by every data type must implement a method called hashCode()(which returns a 32-bit integer). The implementation of hashCode() for an object must be consistent with equals. That is, is a.equals(b) is true, then a.hashCode() must have the same numerical value as b.hashCode(). If the hashCode() values are the same, the objects may or may not be equals, and we must use equals() to decide which condition holds.


Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Live - solving the jasper report out of memory and high cpu usage problems

I still can not find the solution. So I summary all the things and tell my boss about it. If any one knows the solution, please let me know.

Symptom: 1.The JVM became Out of memory when creating big consumption report 2.Those JRTemplateElement-instances is still there occupied even if I logged out the system
Reason:         1. There is a large number of JRTemplateElement-instances cached in the memory 2.The clearobjects() method in ReportThread class has not been triggered when logging out
Action I tried:      About the Virtualizer: 1.Replacing the JRSwapFileVirtualizer with JRFileVirtualizer 2.Not use any FileVirtualizer for cache the report in the hard disk Result: The japserreport still creating the a large number of JRTemplateElement-instances in the memory     About the work around below,      I tried: item 3(in below work around list) – result: it helps to reduce  the size of the JRTemplateElement Object                Item 4,5 – result : it helps a lot to reduce the number of  JRTemplateE…