Hashed array tree
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಹ್ಯಾಶ್ಡ್ ಅರೇ ಟ್ರೀ (ಎಚ್ಎಟಿ) ಎಂಬುದು 1996 ರಲ್ಲಿ ಎಡ್ವರ್ಡ್ ಸಿತಾರ್ಸ್ಕಿ ಪ್ರಕಟಿಸಿದ ಡೈನಾಮಿಕ್ ಅರೇ ಡೇಟಾ-ಸ್ಟ್ರಕ್ಚರ್ ಆಗಿದ್ದು, ದತ್ತಾಂಶ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಪ್ರತ್ಯೇಕ ಮೆಮೊರಿ ತುಣುಕುಗಳ (ಅಥವಾ "ಲೀವ್ಸ್") ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ, ಸರಳ ಡೈನಾಮಿಕ್ ಸರಣಿಗಳಿಗಿಂತ ಭಿನ್ನವಾಗಿ, ಇದು ತಮ್ಮ ಡೇಟಾವನ್ನು ಒಂದು ಸಮೀಪದ ಮೆಮೊರಿ ಪ್ರದೇಶದಲ್ಲಿ ನಿರ್ವಹಿಸುತ್ತದೆ. ಸ್ವಯಂಚಾಲಿತ ಶ್ರೇಣಿಯನ್ನು ಮರುಗಾತ್ರಗೊಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಗಳ ಕಾರಣದಿಂದಾಗಿ ಅಂಶದ ನಕಲು ಪ್ರಮಾಣವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಮತ್ತು ಮೆಮೊರಿ ಬಳಕೆಯ ಮಾದರಿಗಳನ್ನು ಸುಧಾರಿಸುವುದು ಇದರ ಪ್ರಾಥಮಿಕ ಉದ್ದೇಶವಾಗಿದೆ. ಜ್ಯಾಮಿತೀಯ ವಿಸ್ತರಣೆ ತ್ಯಾಜ್ಯ ರೇಖೀಯ (ω (n)) ಜಾಗವನ್ನು ಆಧರಿಸಿದ ಸರಳ ಕ್ರಿಯಾತ್ಮಕ ಸರಣಿಗಳು, ಇಲ್ಲಿ n ಎಂಬುದು ರಚನೆಯಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ, ಹ್ಯಾಶ್ ರಚನೆಯ ಮರಗಳು ಕೇವಲ O () ಶೇಖರಣಾ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ವ್ಯರ್ಥ ಮಾಡುತ್ತವೆ. ಅಲ್ಗಾರಿದಮ್ನ ಆಪ್ಟಿಮೈಸೇಶನ್ ವ್ಯರ್ಥವಾದ ಜಾಗವನ್ನು ಹೆಚ್ಚಿಸುವ ವೆಚ್ಚದಲ್ಲಿ ಡೇಟಾವನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ನಕಲಿಸುವುದನ್ನು ತೆಗೆದುಹಾಕಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಇದು ಸ್ಥಿರವಾದ (ಒ (1)) ಸಮಯದಲ್ಲಿ ಪ್ರವೇಶವನ್ನು ನಿರ್ವಹಿಸಬಲ್ಲದು, ಆದರೆ ಸರಳ ಕ್ರಿಯಾತ್ಮಕ ಸರಣಿಗಳಿಗಿಂತ ಸ್ವಲ್ಪ ನಿಧಾನವಾಗಿರುತ್ತದೆ. ಹ್ಯಾಶ್ ರಚನೆಯ ಮರದ ಕೊನೆಯಲ್ಲಿ ವಸ್ತುಗಳ ಸರಣಿಯನ್ನು ಸೇರಿಸುವಾಗ ಅಲ್ಗಾರಿದಮ್ ಒ (1) ಅಮೋರ್ಟೈಸ್ಡ್ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೊಂದಿದೆ. ಅದರ ಹೆಸರಿಗೆ ವಿರುದ್ಧವಾಗಿ, ಇದು ಹ್ಯಾಶ್ ಕಾರ್ಯಗಳನ್ನು ಬಳಸುವುದಿಲ್ಲ. ವ್ಯಾಖ್ಯಾನಗಳು ಸಿತಾರ್ಸ್ಕಿಯಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲ್ಪಟ್ಟಂತೆ, ಹ್ಯಾಶ್ ರಚನೆಯ ಮರವು ಎರಡು ಸಂಖ್ಯೆಯ ಎಲೆಗಳ ವ್ಯೂಹಗಳ ಶಕ್ತಿಯನ್ನು ಹೊಂದಿರುವ ಉನ್ನತ ಮಟ್ಟದ ಕೋಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಎಲ್ಲಾ ಎಲೆಗಳ ವ್ಯೂಹಗಳು ಉನ್ನತ ಮಟ್ಟದ ಕೋಶದ ಗಾತ್ರಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತವೆ. ಈ ರಚನೆಯು ಮೇಲ್ನೋಟಕ್ಕೆ ವ್ಯೂಹ-ಆಧಾರಿತ ಘರ್ಷಣೆ ಸರಪಳಿಗಳನ್ನು ಹೊಂದಿರುವ ಹ್ಯಾಶ್ ಟೇಬಲ್ ಅನ್ನು ಹೋಲುತ್ತದೆ, ಇದು ಹ್ಯಾಶ್ ರಚನೆಯ ಮರದ ಹೆಸರಿಗೆ ಆಧಾರವಾಗಿದೆ. ಪೂರ್ಣ ಹ್ಯಾಶ್ ರಚನೆಯ ಮರವು m2 ಅಂಶಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳಬಹುದು, ಅಲ್ಲಿ m ಎಂಬುದು ಉನ್ನತ ಮಟ್ಟದ ಕೋಶದ ಗಾತ್ರವಾಗಿದೆ. ಎರಡು ಶಕ್ತಿಗಳ ಬಳಕೆಯು ಭಾಗ ಮತ್ತು ಉಳಿದ ಅಂಕಗಣಿತದ ಕಾರ್ಯಾಚರಣೆಗಳ ಬದಲಿಗೆ ಬಿಟ್ ಕಾರ್ಯಾಚರಣೆಗಳ ಮೂಲಕ ವೇಗವಾಗಿ ಭೌತಿಕ ವಿಳಾಸವನ್ನು ಶಕ್ತಗೊಳಿಸುತ್ತದೆ ಮತ್ತು ವಿಸ್ತರಿಸುತ್ತಿರುವಾಗ ಸಾಂದರ್ಭಿಕ ಜಾಗತಿಕ ರಚನೆಯ ನಕಲಿನ ಉಪಸ್ಥಿತಿಯಲ್ಲಿ ಅನುಬಂಧ ಕಾರ್ಯಾಚರಣೆಯ ಒ (1) ಅಮೋರ್ಟೈಸ್ಡ್ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಖಾತ್ರಿಪಡಿಸುತ್ತದೆ. ವಿಸ್ತರಣೆಗಳು ಮತ್ತು ಗಾತ್ರ ಕಡಿತಗಳು ಸಾಮಾನ್ಯ ಕ್ರಿಯಾತ್ಮಕ ಶ್ರೇಣಿಯ ಜ್ಯಾಮಿತೀಯ ವಿಸ್ತರಣೆಯ ಯೋಜನೆಯಲ್ಲಿ, ಶ್ರೇಣಿಯನ್ನು ಅದರ ಪ್ರಸ್ತುತ ಗಾತ್ರಕ್ಕಿಂತ ಎರಡು ಪಟ್ಟು ಹೊಸ ಗಾತ್ರದೊಂದಿಗೆ ಮೆಮೊರಿಯ ಸಂಪೂರ್ಣ ಅನುಕ್ರಮ ಭಾಗವಾಗಿ ಮರುಹೊಂದಿಸಲಾಗುತ್ತದೆ (ಮತ್ತು ಸಂಪೂರ್ಣ ಡೇಟಾವನ್ನು ನಂತರ ಹೊಸ ಸ್ಥಳಕ್ಕೆ ಸ್ಥಳಾಂತರಿಸಲಾಗುತ್ತದೆ). ಇದು ಒ (ಎನ್) ವ್ಯರ್ಥ ಜಾಗದ ವೆಚ್ಚದಲ್ಲಿ ಒ (1) ಸಾಲ ಮರುಪಾವತಿ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಖಾತ್ರಿಪಡಿಸುತ್ತದೆ, ಏಕೆಂದರೆ ವಿಸ್ತರಿಸಿದ ಶ್ರೇಣಿಯನ್ನು ಅದರ ಹೊಸ ಸಾಮರ್ಥ್ಯದ ಅರ್ಧದಷ್ಟು ತುಂಬಿಸಲಾಗುತ್ತದೆ. ಹ್ಯಾಶ್ಡ್ ಅರೇ ಟ್ರೀ ತುಂಬಿದಾಗ, ಹೆಚ್ಚುವರಿ ಅನುಬಂಧ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಅವಕಾಶ ಕಲ್ಪಿಸಲು ಅದರ ಡೈರೆಕ್ಟರಿ ಮತ್ತು ಎಲೆಗಳನ್ನು ಅವುಗಳ ಹಿಂದಿನ ಗಾತ್ರಕ್ಕಿಂತ ಎರಡು ಪಟ್ಟು ದೊಡ್ಡದಾಗಿ ಪುನರ್ರಚಿಸಬೇಕು. ಹಳೆಯ ರಚನೆಯಲ್ಲಿ ಇರಿಸಲಾಗಿರುವ ದತ್ತಾಂಶವನ್ನು ನಂತರ ಹೊಸ ಸ್ಥಳಗಳಿಗೆ ಸ್ಥಳಾಂತರಿಸಲಾಗುತ್ತದೆ. ನಂತರ ಕೇವಲ ಒಂದು ಹೊಸ ಎಲೆಯನ್ನು ಹಂಚಲಾಗುತ್ತದೆ ಮತ್ತು ಮೇಲ್ಭಾಗದ ಶ್ರೇಣಿಯಲ್ಲಿ ಸೇರಿಸಲಾಗುತ್ತದೆ, ಹೀಗಾಗಿ ಅದು ಅದರ ಹೊಸ ಸಾಮರ್ಥ್ಯದ ಕಾಲು ಭಾಗಕ್ಕೆ ಮಾತ್ರ ತುಂಬುತ್ತದೆ. ಎಲ್ಲಾ ಹೆಚ್ಚುವರಿ ಎಲೆಗಳನ್ನು ಇನ್ನೂ ಹಂಚಿಕೆ ಮಾಡಲಾಗಿಲ್ಲ, ಮತ್ತು ಅಗತ್ಯವಿದ್ದಾಗ ಮಾತ್ರ ಹಂಚಿಕೆ ಮಾಡಲಾಗುತ್ತದೆ, ಹೀಗಾಗಿ ಶೇಖರಣೆಯ ಒ () ಮಾತ್ರ ವ್ಯರ್ಥವಾಗುತ್ತದೆ. ಗಾತ್ರವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಅನೇಕ ಪರ್ಯಾಯಗಳಿವೆಃ ಹ್ಯಾಶ್ ರಚನೆಯ ಮರವು ಎಂಟನೇ ಒಂದು ಪೂರ್ಣವಾಗಿದ್ದಾಗ, ಅದನ್ನು ಸಣ್ಣ, ಅರ್ಧ ತುಂಬಿದ ಹ್ಯಾಶ್ ರಚನೆಯ ಮರವಾಗಿ ಪುನರ್ರಚಿಸಬಹುದು; ಮತ್ತೊಂದು ಆಯ್ಕೆಯು ಎಲೆಗಳನ್ನು ಮರುಗಾತ್ರಗೊಳಿಸದೆ, ಬಳಕೆಯಾಗದ ಎಲೆ ಸರಣಿಗಳನ್ನು ಮಾತ್ರ ಮುಕ್ತಗೊಳಿಸುವುದು. ಅಗತ್ಯವಿರುವಂತೆ ಕೋಶದ ಶ್ರೇಣಿಯನ್ನು ಬೆಳೆಸುವಾಗ, ಬಹುಶಃ ಜ್ಯಾಮಿತೀಯ ವಿಸ್ತರಣೆಯ ಮೂಲಕ, ಮರುಗಾತ್ರಗೊಳಿಸದೆ ಹೊಸ ಎಲೆಗಳನ್ನು ಸೇರಿಸುವುದು ಹೆಚ್ಚಿನ ಆಪ್ಟಿಮೈಸೇಶನ್ಗಳಲ್ಲಿ ಸೇರಿದೆ. ಇದು ವ್ಯರ್ಥವಾದ ಜಾಗವನ್ನು ಒ (ಎನ್) ಆಗಿ ಮಾಡುವ ವೆಚ್ಚದಲ್ಲಿ ದತ್ತಾಂಶವನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ನಕಲಿಸುವ ಅಗತ್ಯವನ್ನು ತೊಡೆದುಹಾಕುತ್ತದೆ, ಸಣ್ಣ ಸ್ಥಿರಾಂಕದೊಂದಿಗೆ, ಮತ್ತು ನಿಗದಿತ ಮಿತಿ ಓವರ್ಹೆಡ್ ತಲುಪಿದಾಗ ಮಾತ್ರ ಪುನರ್ರಚನೆಯನ್ನು ಮಾಡುತ್ತದೆ. ಸಂಬಂಧಿತ ದತ್ತಾಂಶ ರಚನೆಗಳು ಬ್ರಾಡ್ನಿಕ್ ಮತ್ತು ಇತರರು. ಅರೇ ಮರಗಳನ್ನು ಹ್ಯಾಶ್ ಮಾಡಲು ಇದೇ ರೀತಿಯ ಸ್ಥಳ ವ್ಯರ್ಥ ಪ್ರೊಫೈಲ್ನೊಂದಿಗೆ ಡೈನಾಮಿಕ್ ಅರೇ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲಾಗಿದೆ. ಬ್ರಾಡ್ನಿಕ್ನ ಅನುಷ್ಠಾನವು ಈ ಹಿಂದೆ ನಿಗದಿಪಡಿಸಿದ ಎಲೆ ಸರಣಿಗಳನ್ನು ಉಳಿಸಿಕೊಂಡಿದೆ, ಹ್ಯಾಶ್ ಮಾಡಿದ ಸರಣಿ ಮರಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ ವಿಳಾಸ ಲೆಕ್ಕಾಚಾರ ಕಾರ್ಯವನ್ನು ಹೊಂದಿದೆ. ಡೈನಾಮಿಕ್ ಅರೇ ಅನ್ ರೋಲ್ಡ್ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಬಿ-ಟ್ರೀ ರೆಫೆರೆನ್ಸ್ ಅರೇಗಳನ್ನು ಸಹ ನೋಡಿ