La respuesta depende tanto del idioma como de la implementación específica. Para los lenguajes que admiten OOP con jerarquías de clases estáticas (en tiempo de compilación) y listas de métodos, como C ++, C # y Java, el mecanismo de búsqueda típico funciona de la siguiente manera:
- El objeto contiene un puntero a una tabla de búsqueda. En C ++, este puntero se llama tradicionalmente el puntero vtbl (puntero de tabla virtual), pero la existencia de ese puntero, y mucho menos su nombre, no está especificada ni obligada por el estándar.
- La tabla de búsqueda (vtbl) suele ser una matriz simple que contiene punteros a métodos (es decir, punteros de función). El vtbl también puede contener otra información, como compensaciones a subobjetos de clase base en el caso de herencia múltiple y / o información de tipo de tiempo de ejecución.
- El compilador asigna un pequeño índice entero a cada mensaje (el término OO para un método que aún no se ha resuelto == función virtual en C ++). El algoritmo para asignar estos índices es algo así como: comenzar con el primer mensaje en la clase más básica de la jerarquía de clases y numerar cada mensaje secuencialmente. En cada clase derivada, comience a numerar desde donde la dejó, pero no renumere los mensajes anulados: los mensajes en la clase derivada que anulan el mismo mensaje en la clase base obtienen el mismo índice que el mensaje en la clase base. Estos índices corresponden a entradas en la tabla de búsqueda.
- Cuando se invoca un mensaje en un objeto, el índice de ese mensaje se busca en la tabla de búsqueda (que es una matriz simple) para obtener un puntero de método. Ese método se llama entonces.
Para lenguajes como JavaScript y Perl, donde los métodos se pueden agregar dinámicamente y pueden surgir nuevas subclases en tiempo de ejecución, las estructuras de datos y los algoritmos son un poco diferentes.
- Cada objeto contiene una tabla de búsqueda que contiene una asignación de nombres de mensajes a métodos.
- La tabla de búsqueda podría ser una tabla hash, tecleada en el nombre del método, o podría ser una matriz lineal de nombre-valor en orden ordenado, o alguna variante de la misma. Básicamente, la implementación puede usar cualquier estructura de datos que produzca una búsqueda razonablemente rápida.
- La implementación puede pre-hash todos los nombres de mensajes para la eficiencia, o no. Hay numerosas compensaciones espacio-temporales a considerar. Las matrices ordenadas de nombre-valor se pueden buscar con búsqueda binaria y requieren menos memoria. Las tablas hash son más rápidas, pero usan más memoria y tienden a causar más fragmentación de memoria.
- El proceso que tiene lugar cuando se llama a un mensaje en un objeto es similar al proceso descrito anteriormente. El nombre del mensaje (o su hash precalculado) se busca en la tabla de búsqueda del objeto, luego el control se envía al método resultante.
Debo señalar que lo anterior es mi comprensión de la práctica real. En realidad, hay varias otras formas de implementar la semántica de los idiomas. Por ejemplo, en lugar de incrustar el puntero vtbl en el objeto, puede ser parte del identificador de objeto. Las búsquedas también podrían revertirse, con tablas de búsqueda adjuntas a los mensajes y la búsqueda basada en el tipo de objeto, en lugar de al revés.
- ¿Aprender las estructuras de datos y las matemáticas será una "reinvención de la rueda"?
- ¿Cómo se desarrollaron los algoritmos cuánticos?
- ¿Cuál es el mejor algoritmo de clasificación manual? Por ejemplo, si tuviera una pila de papeles que quisiera ordenar alfabéticamente, ¿cuál sería la forma más eficiente de hacerlo? ¿Qué pasaría si estuvieras de acuerdo con que uno o dos se alejen de su posición ordenada?
- ¿Cuáles son algunos lenguajes de programación que me permiten visualizar algoritmos?
- ¿Cómo puedo encontrar la ruta más larga de un gráfico bidireccional utilizando el algoritmo BFS?
