자바 데이터 구조 (해시 표)

3243 단어 데이터 구조
해시 시계
1. 해시 표 는 무엇 입 니까?
    해시 표 는 빠 른 삽입 작업 과 검색 작업 을 제공 하 는 데이터 구조 이다.그것 은 배열 에 기초 하여 이 루어 진다.
2. 해시 화
    1) 키 워드 를 직접 색인 으로 한다.
    2) 단 어 를 색인 으로 변환 합 니 다.
        <1 > 알파벳 을 ASCII 코드 로 변환 하여 추가
        <2 > 멱 의 연승
        <3 > 압축 선택 값
3. 압축 후에 도 발생 할 수 있 는 문제.
    충돌: 모든 단어 가 배열 의 공백 단원 에 비 치 는 것 을 보장 할 수 없습니다.
    해결 방법:
        <1 > 주소 법 열기
        <2 > 체인 주소 법
/** 
 *       
 * @author Administrator 
 * 
 */ 
public class Info { 
    private String key; 
    private String name; 
 
    public Info(String key, String name) { 
        this.key = key; 
        this.name = name; 
    } 
 
    public String getKey() { 
        return key; 
    } 
 
    public void setKey(String key) { 
        this.key = key; 
    } 
 
    public String getName() { 
        return name; 
    } 
 
    public void setName(String name) { 
        this.name = name; 
    } 
}
import java.math.BigInteger; 
 
public class HashTable { 
    private Info[] arr; 
 
    /** 
     *         
     */ 
    public HashTable() { 
        arr = new Info[100]; 
    } 
 
    /** 
     *           
     */ 
    public HashTable(int maxSize) { 
        arr = new Info[maxSize]; 
    } 
 
    /** 
     *      
     */ 
    public void insert(Info info) { 
        arr[hashCode(info.getKey())] = info; 
    } 
 
    /** 
     *      
     */ 
    public Info find(String key) { 
        return arr[hashCode(key)]; 
    } 
 
    public int hashCode(String key) { 
//      int hashVal = 0; 
//      for(int i = key.length() - 1; i >= 0; i--) { 
//          int letter = key.charAt(i) - 96; 
//          hashVal += letter; 
//      } 
//      return hashVal; 
 
        BigInteger hashVal = new BigInteger("0"); 
        BigInteger pow27 = new BigInteger("1"); 
        for(int i = key.length() - 1; i >= 0; i--) { 
            int letter = key.charAt(i) - 96; 
            BigInteger letterB = new BigInteger(String.valueOf(letter)); 
            hashVal = hashVal.add(letterB.multiply(pow27)); 
            pow27 = pow27.multiply(new BigInteger(String.valueOf(27))); 
        } 
        return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue(); 
    } 
} 
public class TestHashTable { 
    public static void main(String[] args) { 
        HashTable ht = new HashTable(); 
        ht.insert(new Info("a","  ")); 
        ht.insert(new Info("ct","  ")); 
        ht.insert(new Info("wangwu","  ")); 
 
        System.out.println(ht.find("a").getName()); 
        System.out.println(ht.find("ct").getName()); 
    } 
} 

좋은 웹페이지 즐겨찾기