데이터 구조의 간단 한 해시

9474 단어 데이터 구조
데이터 구조의 간단 한 해시           문 제 를 보 는 것 은 그리 익숙 하지 않 을 수도 있 고 데이터 구조 에서 하 쉬 가 사용 하 는 것 이 비교적 적다.그러나 배열 (대기 열) 이나 링크 라 고 하면 모두 가 좀 좋아 질 것 입 니 다. 이것 은 우리 가 프로 그래 밍 에서 자주 사용 하 는 데이터 구조 이기 때 문 입 니 다.           이 글 은 주로 간단 한 hash 구 조 를 소개 하 는데, 이 문장 을 읽 기 에 그리 힘 들 지 않 게 하기 위해 서 이다.나 는 모두 가 알 고 있 는 배열 과 링크 에서 간단 한 해시 구조 로 넘 어 갈 것 이다.        배열 의 장점:           배열 의 장점 은 그의 검색 이 편리 하 다 는 것 이다. 아래 표 시 된 색인 만 사용 하면 배열 에 해당 하 는 우리 가 배열 에 저장 한 물건 을 매우 빠 르 고 편리 하 게 찾 을 수 있다 는 것 이다.            배열 의 단점:           배열 의 큰 단점 중 하 나 는 하나의 배열 을 예화 할 때 반드시 해당 하 는 메모리 공간 을 분배 해 야 한 다 는 것 이다. 즉, 하나의 배열 이 그의 크기 를 만 들 면 고정 된다 는 것 이다.이렇게 하면 문제 가 발생 할 수 있다. 초기 화 된 메모리 공간 이 작고 저 장 된 데이터 가 적다.초기 화 된 공간 이 너무 크 면 공간의 낭 비 를 초래 할 수 있다.한편, 우리 가 배 운 대열 은 그 중의 일부 문 제 를 해결 할 수 있다. 대열 은 배열 의 패 키 징 작업 으로 배열 의 길이 에 대한 동적 증 삭 을 실현 한다.대기 열 실질 적 으로 도 하나의 배열 로 데 이 터 를 저장 하고 있 기 때문에 배열 에 존재 하 는 일부 문 제 는 해결 되 지 않 았 다.예 를 들 어 저 장 된 데이터 가 많 을 때 대기 열 로 이 루어 지지 않 습 니 다 (마지막 으로 저장 할 때 도 매우 큰 배열 로 저장 합 니 다. 이 문 제 는 배열 과 같 습 니 다).           대기 열의 단점:           대기 열의 단점 은 데 이 터 를 삭제 하고 삽입 하 는 것 입 니 다. 코드 를 사용 하 는 것 은 우리 가 봉 인 된 코드 이기 때 문 일 수도 있 습 니 다. 코드 한 마디 만 있 으 면 실행 할 수 있 지만 내부 의 작업량 이 매우 많 습 니 다. 열 을 사용 한 사람 은 모두 알 고 있 습 니 다. 대기 열 에 데 이 터 를 임의로 삽입 합 니 다. 예 를 들 어 대기 열 에 삽입 한 색인 값 이 0 인 위치 입 니 다.이것 은 뒤의 모든 데이터 의 위 치 를 뒤로 이동 시 킬 수 있다.이렇게 하면 전체 프로그램의 효율 을 떨 어 뜨 릴 것 이다.          링크 의 장점:           한편, 링크 의 장점 에 대해 대열 이 데 이 터 를 추가 삭제 할 때의 단점 을 보완 했다.링크 는 데 이 터 를 삭제 하고 증가 할 때 해당 노드 의 방향 을 바 꾸 면 됩 니 다.           링크 의 단점:           그러나 링크 는 배열 의 장점 이 없어 서 링크 의 단점 을 찾 았 다.찾 을 때마다 링크 를 옮 겨 다 녀 야 합 니 다.           왜 hash 를 써 요?           둘 다 장점 이 있 는 만큼 우 리 는 둘 의 장점 을 결합 시 킬 수 있 을 까?답 은 돼.                       두 가지 생각 을 결합 하 다.           대기 열 은 배열 에 대한 패 키 징 작업 입 니 다.그러면 우리 가 배열 과 링크 를 한데 묶 어서 조작 하면 배열 과 링크 의 장점 을 교묘 하 게 결합 시 킬 수 있다.본 고 에서 소개 하고 자 하 는 간단 한 hash 는 바로 이런 방법 으로 이 루어 진 것 이다.                     우리 함께 생각해 보 자. 만약 에 그런 배열 이 있다 면 배열 에 저 장 된 것 은 하나의 노드 이 고 노드 아래 는 그의 키 노드 이다. 그러면 배열 과 링크 가 결합 된다.그렇다면 이런 구 조 는 위 에서 말 한 것 에 비해 어떤 장점 이 있 을 까?다음은 제 가 그의 장점 을 말씀 드 리 겠 습 니 다.           1. 배열 의 아래 표 시 를 이용 하여 우 리 는 다음 표 에 대응 하 는 링크 를 빨리 찾 을 수 있다.(배열 의 장점)           2. 데 이 터 는 노드 로 저장 되 기 때문에 데 이 터 를 삭제 할 때 링크 의 장점 도 충분히 나타난다.(링크 의 장점)           3. 배열 만 보고 아래 에 걸 려 있 는 링크 가 있 으 면 저장 할 수 있 는 데 이 터 량 이 많아 집 니 다.(배열 만 있 을 때 보다)           생각 속 의 문제:           여기 서 문제 가 하나 있 습 니 다. 찾 을 때 해당 링크 를 빨리 찾 을 수 있 지만 전체 링크 에서 우리 가 필요 로 하 는 데 이 터 를 찾 아야 합 니 다. 링크 가 너무 길 면 링크 가 찾 는 단점 이 나타 납 니 다.이런 상황 을 피하 기 위해 서우 리 는 하나의 밸브 값 을 설정 해 야 한다. 데이터 저장량 과 배열 의 길이 가 특정한 값 보다 크 면 배열 의 길 이 를 늘 린 다음 에 데 이 터 를 저장 하 는 방법 에 따라 저 장 된 데 이 터 를 다시 저장 해 야 한다.이렇게 하면 어떤 체인 시계 가 너무 큰 것 을 피 할 수 있 을 것 이다.                      실현:           다음은 어떻게 프로 그래 밍 으로 우리 위의 생각 을 실현 하 는 지 소개 한다.           어떻게 데 이 터 를 저장 합 니까? 저장 할 데 이 터 는 키 워드 를 가 져 가 야 합 니 다. (키 워드 는 달라 야 합 니 다)           다음은 qq 사용자 정 보 를 저장 하 는 것 을 예 로 들 자.           qq 번 호 는 다 달라 요.따라서 사용자 정 보 를 저장 할 키워드 로 qq 번 호 를 사용 할 수 있 습 니 다.           각 qq 번 호 는 하나의 맵 을 통 해 배열 의 아래 표 시 를 대응 합 니 다.이 맵 은 바로 hash 알고리즘 입 니 다. 물론 이 알고리즘 은 우리 가 스스로 설정 합 니 다.하지만 맵 을 통 해 얻 은 배열 의 하 표 는 경 계 를 넘 을 수 없습니다.           증가:           우 리 는 이 알고리즘 을 배열 의 길 이 를 나 누 어 나머지 를 우리 가 매 핑 한 데이터 로 간단하게 정의 합 니 다.           1. 그래서 int hash () 방법 을 정의 하고 돌아 오 는 맵 값

//  boolean is_searched=false;
	boolean is_removed=false;
	boolean is_reseted=false;
	//      
	private Node[] array;
	//      
	private int size;
	//    
	private double fa_value=0.8;
	//         
	private int sum=0;
/**
	 *   hash  
	 * @param qq
	 * @return
	 */
	private int hash(QQ qq){
		return qq.getNumber()%size;
	}

2. 맵 을 통 해 얻 은 배열 아래 표 시 를 하면 데 이 터 를 저장 할 수 있 습 니 다.                       이 값 에 대응 하 는 배열 요소 가 비어 있 으 면 데 이 터 를 저장 할 수 있 습 니 다. 한 노드 를 예화 하고 데 이 터 를 노드 속성 값 으로 설정 한 다음 에 노드 를 배열 에 저장 할 수 있 습 니 다.                        비어 있 지 않 으 면 빈 배열 요소 (즉 노드) 가 아 닌 바이트 가 비어 있 는 지 판단 하고 비어 있 으 면 노드 를 예화 하고 하위 노드 로 저장 합 니 다.비어 있 지 않 으 면 아래 의 하위 노드 로 판단 합 니 다.빈 위치 로 판단 할 때 까지 데 이 터 를 굵게 합 니 다.
/**
	 *        
	 * @param qq
	 * @return
	 */
	public boolean add(QQ qq){
		//           
		if(((double)sum/size)>fa_value){
			rehash();//      ,    
		}
		//  qq        
		int index = hash(qq);
		//  node   null
		if(array[index]==null){
			//      QQ    
			array[index]=new Node(qq);
			sum++;
			return true;
		}else{
			is_kong(array[index], qq);
			return true;

			
		}
	}
	/**
	 *        ,             。           
	 * @param node
	 */
	private void is_kong(Node node,QQ qq){
		if(node.getNext()==null){
			//                 
			Node childnode=new Node(qq);
			node.setNext(childnode);
			System.out.println("      ");
			sum++;
		}else{
			//            
			is_kong(node.getNext().getNext(),qq);
		}
	}
/**
	 *   array
	 */
	private void rehash(){
		sum=0;
		//       ,          
		size*=2;
		Node[] array2=new Node[size];
		Node[] array3=array;
		array=array2;
		//       
		for(int i=0;i<array3.length;i++){
			//                
			if(array3[i]!=null){
				add(array3[i].getData());
	
			}
			
		}
	}

찾기:           물론 키워드 qq 번 호 를 이용 하여 사용자 정 보 를 찾 을 수 있 습 니 다.                      1. qq 번 호 를 이용 하여 hash 알고리즘 을 통 해 얻 은 매 핑 값 은 서로 의존 하 는 배열 요소 (하나의 노드 이 고 긴 체인 으로 이해 할 수 있 습 니 다) 를 찾 으 면 우리 가 찾 아야 할 데 이 터 는 이 노드 나 노드 아래 의 하위 노드 에 있 습 니 다.이 데이터 가 이 구조 안에 존재 하지 않 는 한                      2. 아래 표 시 된 배열 요 소 를 추출 하여 이 요소 가 비어 있 는 지 판단 합 니 다.                      비어 있 지 않 으 면 노드 의 데이터 속성 이 같 는 지 판단 하고 같 으 면 찾 을 수 있 습 니 다.다 르 면 뒤쪽 부분 으로 찾 아 보 세 요.           중대 의 결말 까지.비어 있 으 면 이 사용자 의 정보 가 존재 하지 않 는 다 고 판단 합 니 다.           아래 에서 얻 은 요소 가 비어 있 으 면 사용자 정보 가 존재 하지 않 는 다 고 판단 할 수 있 습 니 다.
/**
	 *   qq      
	 * @param qqnumber
	 */
	public boolean search(int qqnumber){
		is_searched=false;
		//    
		for(int i=0;i<array.length;i++){
			if(array[i]!=null){
				//  qq   
				if(array[i].getData().getNumber()==qqnumber){
					System.out.println("         :"+
							array[i].getData().getName()+"   " +
									"qq  :"+array[i].getData().getNumber());
					is_searched=true;
				}else{
					 bianli(array[i].getNext(),qqnumber);
				}
			}
		}
		return is_searched;
	}
	/**
	 *          
	 * @param node
	 */
	private void bianli(Node node,int qqnumber){
		//        
		if(node!=null){
			//  qq   
			if(node.getData().getNumber()==qqnumber){
				System.out.println("         :"+
						node.getData().getName()+"   " +
								"qq  :"+node.getData().getNumber());
				is_searched=true;
			}else{
				//  qq    
				 bianli(node.getNext(),qqnumber);
			}
		}
	}

          삭제:
           1. 찾기 와 같 습 니 다.데 이 터 를 찾 을 때 데 이 터 를 저장 하 는 노드 에 하위 노드 가 있 으 면 이 노드 를 하위 노드 로 대체 하면 됩 니 다.
/**
	 *   qq     
	 * @param qqnumber
	 */
	public boolean remove(int qqnumber){
		is_removed=false;
		//    
		for(int i=0;i<array.length;i++){
			if(array[i]!=null){
				//  qq   
				if(array[i].getData().getNumber()==qqnumber){
					if(array[i].getNext()==null){
						//         
						array[i]=null;
						is_removed=true;
					}else{
						array[i]=array[i].getNext();
					}
				}else{
					bianli2(array[i],qqnumber);
				}
			}
		}
		return is_removed;
	}
	/**
	 *          
	 * @param node
	 */
	private void bianli2(Node node,int qqnumber){
		//        
		if(node.getNext()!=null){
			//     qq   
			if(node.getNext().getData().getNumber()==qqnumber){
				node.setNext(node.getNext().getNext());
				System.out.println("    !!");
				is_removed=true;
			}
		}else{
			return;
		}
	}

    수정:           위 에 있 는 거 있 으 면 이거 쉬 워.해당 데이터 에 대응 하 는 노드 를 찾 으 면 노드 데이터 속성 을 바 꾸 면 ok 입 니 다.
/**
	 *   qq       
	 * @param qqnumber
	 */
	public boolean reSet(int qqnumber,String newname){
		is_reseted=false;
		//    
		for(int i=0;i<array.length;i++){
			if(array[i]!=null){
				//  qq   
				if(array[i].getData().getNumber()==qqnumber){
					array[i].getData().setName(newname);
					is_reseted=true;
				}else{
					bianli3(array[i],qqnumber,newname);
				}
			}
		}
		return is_reseted;
	}
	/**
	 *   
	 * @param node
	 * @param newname
	 */
	private void bianli3(Node node,int qqnumber,String newname){
		if(node.getNext()!=null){
			if(node.getNext().getData().getNumber()==qqnumber){
				node.getNext().getData().setName(newname);
				is_reseted=true;
			}else{
				bianli3(node.getNext().getNext(),qqnumber,newname);
			}
		}else{
			return ;
		}
	}

좋은 웹페이지 즐겨찾기